Codeforces Round #329 (Div. 2)

时间：2021-08-08 21:01:12

推迟了15分钟开始，B卡住不会，最后弃疗，rating只涨一分。。。

 

水(暴力枚举) A - 2Char

/************************************************

* Author        :Running_Time

* Created Time  :2015/11/4 星期三 21:33:17

* File Name     :A.cpp

 ************************************************/

#include <cstdio>

#include <algorithm>

#include <iostream>

#include <sstream>

#include <cstring>

#include <cmath>

#include <string>

#include <vector>

#include <queue>

#include <deque>

#include <stack>

#include <list>

#include <map>

#include <set>

#include <bitset>

#include <cstdlib>

#include <ctime>

using namespace std;

#define lson l, mid, rt << 1

#define rson mid + 1, r, rt << 1 | 1

typedef long long ll;

const int N = 1e5 + 10;

const int INF = 0x3f3f3f3f;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = acos (-1.0);

char s[110][1010];

int len[110];

bool ok[110];

vector<char> vec[110];

int main(void)    {

	int n;	scanf ("%d", &n);

	for (int i=1; i<=n; ++i)	{

		scanf ("%s", s[i] + 1);

		len[i] = strlen (s[i] + 1);

	}

	memset (ok, true, sizeof (ok));

	int vis[30];

	for (int i=1; i<=n; ++i)	{

		memset (vis, 0, sizeof (vis));

		int tot = 0;

		for (int j=1; j<=len[i]; ++j)	{

			if (!vis[s[i][j]-'a'])	{

                vec[i].push_back (s[i][j]);

				vis[s[i][j]-'a'] = 1;	tot++;

			}

			else	continue;

			if (tot > 2)	{

				ok[i] = false;	break;

			}

		}

	}

	int ans = 0;

	for (char a='a'; a<='z'; ++a)	{

		for (char b='a'; b<='z'; ++b)	{

			int tmp = 0;

			for (int i=1; i<=n; ++i)	{

				if (!ok[i])	continue;

				bool flag = true;

                for (int j=0; j<vec[i].size (); ++j)	{

					char c = vec[i][j];

					if (c != a && c != b)	{

						flag = false;

					}

                }

                if (flag)	tmp += len[i];

			}

			ans = max (ans, tmp);

		}

	}

	printf ("%d\n", ans);

   //cout << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";

    return 0;

}

　

sorting B - Anton and Lines

题意：给了一些直线，问是否在横坐标(x1, x2)范围内有相交的点

分析：很好想到每条直线与x = x1以及x = x2的直线的交点，那么满足相交的条件是y11 < y12 && y12 > y22，也就是逆序对。这样少掉了正好在x1或x2相交的情况，一种方法是L += EPS, R -= EPS，还有一种是排序。还有升级版的问题

/************************************************

* Author        :Running_Time

* Created Time  :2015/11/4 星期三 21:33:17

* File Name     :B_2.cpp

 ************************************************/

#include <cstdio>

#include <algorithm>

#include <iostream>

#include <sstream>

#include <cstring>

#include <cmath>

#include <string>

#include <vector>

#include <queue>

#include <deque>

#include <stack>

#include <list>

#include <map>

#include <set>

#include <bitset>

#include <cstdlib>

#include <ctime>

using namespace std;

#define lson l, mid, rt << 1

#define rson mid + 1, r, rt << 1 | 1

typedef long long ll;

const int N = 1e6 + 10;

const int INF = 0x3f3f3f3f;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = acos (-1.0);

struct Y	{

    double y1, y2;

    bool operator < (const Y &r) const	{

		return y1 < r.y1;

    }

}y[N];

/*

    快速读入输出(读入输出外挂)!--黑科技

    使用场合：huge input (1e6以上)

*/

inline int read(void)   {

    int f = 1, ret = 0; char ch = getchar ();

    while ('0' > ch || ch > '9')    {

        if (ch == '-')  f = -1;

        ch = getchar ();

    }

    while ('0' <= ch && ch <= '9')  {

        ret = ret * 10 + ch - '0';

        ch = getchar ();

    }

    return ret * f;

}

int main(void)    {

	int n;	scanf ("%d", &n);

	double x1, x2;	scanf ("%lf%lf", &x1, &x2);

	x1 += EPS;	x2 -= EPS;

	double k, b;

	for (int i=1; i<=n; ++i)	{

		scanf ("%lf%lf", &k, &b);

		y[i].y1 = k * x1 + b;

		y[i].y2 = k * x2 + b;

	}

	sort (y+1, y+1+n);

	bool flag = false;

	for (int i=2; i<=n; ++i)	{

		if (y[i].y2 < y[i-1].y2)		{

			flag = true;	break;

		}

	}

	if (flag)	puts ("YES");

	else	puts ("NO");

//	cout << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";

    return 0;

}

　　

/************************************************

* Author        :Running_Time

* Created Time  :2015/11/4 星期三 21:33:17

* File Name     :B.cpp

 ************************************************/

#include <cstdio>

#include <algorithm>

#include <iostream>

#include <sstream>

#include <cstring>

#include <cmath>

#include <string>

#include <vector>

#include <queue>

#include <deque>

#include <stack>

#include <list>

#include <map>

#include <set>

#include <bitset>

#include <cstdlib>

#include <ctime>

using namespace std;

#define lson l, mid, rt << 1

#define rson mid + 1, r, rt << 1 | 1

typedef long long ll;

const int N = 1e6 + 10;

const int INF = 0x3f3f3f3f;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = acos (-1.0);

struct Y	{

    ll y1, y2;

    bool operator < (const Y &r) const	{

		return y1 < r.y1 || (y1 == r.y1 && y2 < r.y2);

    }

}y[N];

/*

    快速读入输出(读入输出外挂)!--黑科技

    使用场合：huge input (1e6以上)

*/

inline int read(void)   {

    int f = 1, ret = 0; char ch = getchar ();

    while ('0' > ch || ch > '9')    {

        if (ch == '-')  f = -1;

        ch = getchar ();

    }

    while ('0' <= ch && ch <= '9')  {

        ret = ret * 10 + ch - '0';

        ch = getchar ();

    }

    return ret * f;

}

int main(void)    {

	int n;	scanf ("%d", &n);

	int x1, x2;	scanf ("%d%d", &x1, &x2);

	ll k, b;

	for (int i=1; i<=n; ++i)	{

		k = read ();	b = read ();

		y[i].y1 = k * x1 + b;

		y[i].y2 = k * x2 + b;

	}

	sort (y+1, y+1+n);

	bool flag = false;

	for (int i=2; i<=n; ++i)	{

		if (y[i].y2 < y[i-1].y2)		{

			flag = true;	break;

		}

	}

	if (flag)	puts ("YES");

	else	puts ("NO");

//	cout << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";

    return 0;

}

　　

相关文章