Suffix Three

\[Time Limit: 1 s\quad Memory Limit: 256 MB
\]

直接按照题意模拟即可。

view

#include <map>

#include <set>

#include <list>

#include <ctime>

#include <cmath>

#include <stack>

#include <queue>

#include <cfloat>

#include <string>

#include <vector>

#include <cstdio>

#include <bitset>

#include <cstdlib>

#include <cstring>

#include <iostream>

#include <algorithm>

#include <unordered_map>

#define  lowbit(x)  x & (-x)

#define  mes(a, b)  memset(a, b, sizeof a)

#define  fi         first

#define  se         second

#define  pb         push_back

#define  pii        pair<int, int>

#define  INOPEN     freopen("in.txt", "r", stdin)

#define  OUTOPEN    freopen("out.txt", "w", stdout)

typedef unsigned long long int ull;

typedef long long int ll;

const int    maxn = 1e5 + 10;

const int    maxm = 1e5 + 10;

const ll     mod  = 1e9 + 7;

const ll     INF  = 1e18 + 100;

const int    inf  = 0x3f3f3f3f;

const double pi   = acos(-1.0);

const double eps  = 1e-8;

using namespace std;

int n, m;

int cas, tol, T;

char s[maxn];

int main() {

	scanf("%d", &T);

	while(T--) {

		scanf("%s", s+1);

		n = strlen(s+1);

		reverse(s+1, s+1+n);

		if(s[1]=='o' && s[2]=='p') {

			puts("FILIPINO");

		} else if(s[1]=='u'&&s[2]=='s'&&s[3]=='e'&&s[4]=='d') {

			puts("JAPANESE");

		} else if(s[1]=='u'&&s[2]=='s'&&s[3]=='a'&&s[4]=='m') {

			puts("JAPANESE");

		} else if(s[1]=='a'&&s[2]=='d'&&s[3]=='i'&&s[4]=='n'&&s[5]=='m') {

			puts("KOREAN");

		}

	}

	return 0;

}

Azamon Web Services

\[Time Limit: 2 s\quad Memory Limit: 256 MB
\]

用 \(p[]\) 记录第一个字符串从 \(i\) 往后最小的字母在哪里。

枚举一对交换字符较左的位置，每次判断的时候只需要把 \(s[i]\) 和 \(s[p[i]]\) 交换，就可以让这个字符串尽量小，然后和第二个字符串比较，看能否满足条件即可。

view

#include <map>

#include <set>

#include <list>

#include <ctime>

#include <cmath>

#include <stack>

#include <queue>

#include <cfloat>

#include <string>

#include <vector>

#include <cstdio>

#include <bitset>

#include <cstdlib>

#include <cstring>

#include <iostream>

#include <algorithm>

#include <unordered_map>

#define  lowbit(x)  x & (-x)

#define  mes(a, b)  memset(a, b, sizeof a)

#define  fi         first

#define  se         second

#define  pb         push_back

#define  pii        pair<int, int>

#define  INOPEN     freopen("in.txt", "r", stdin)

#define  OUTOPEN    freopen("out.txt", "w", stdout)

typedef unsigned long long int ull;

typedef long long int ll;

const int    maxn = 1e5 + 10;

const int    maxm = 1e5 + 10;

const ll     mod  = 1e9 + 7;

const ll     INF  = 1e18 + 100;

const int    inf  = 0x3f3f3f3f;

const double pi   = acos(-1.0);

const double eps  = 1e-8;

using namespace std;

int n, m;

int cas, tol, T;

string s1, s2;

int p[maxn];

int main() {

	scanf("%d", &T);

	while(T--) {

		cin >> s1 >> s2;

		n = s1.size(), m = s2.size();

		for(int i=0; i<n; i++)	p[i] = i;

		int pos = n-1;

		for(int i=n-2; i>=0; i--) {

			if(s1[i] < s1[pos])	pos = i;

			p[i] = pos;

		}

		int flag = 0;

		for(int i=0; i<min(n, m); i++) {

			swap(s1[i], s1[p[i]]);

			if(s1 < s2) {

				flag = 1;

				cout << s1 << endl;

				break;

			}

			swap(s1[i], s1[p[i]]);

		}

		if(!flag)	cout << "---" << endl;

	}

	return 0;

}

Cut and Paste

\[Time Limit: 2 s\quad Memory Limit: 256 MB
\]

由于 \(1 \leq x \leq 10^6\)，所以可以暴力知道前 \(x\) 个字符串长什么样。

当字符串长度超过 \(x\) 时，往后字符串长什么样并不重要，因为光标永远不会到达这里，所以对长度的影响可以直接计算出来。

view

#include <map>

#include <set>

#include <list>

#include <ctime>

#include <cmath>

#include <stack>

#include <queue>

#include <cfloat>

#include <string>

#include <vector>

#include <cstdio>

#include <bitset>

#include <cstdlib>

#include <cstring>

#include <iostream>

#include <algorithm>

#include <unordered_map>

#define  lowbit(x)  x & (-x)

#define  mes(a, b)  memset(a, b, sizeof a)

#define  fi         first

#define  se         second

#define  pb         push_back

#define  pii        pair<int, int>

#define  INOPEN     freopen("in.txt", "r", stdin)

#define  OUTOPEN    freopen("out.txt", "w", stdout)

typedef unsigned long long int ull;

typedef long long int ll;

const int    maxn = 1e5 + 10;

const int    maxm = 1e5 + 10;

const ll     mod  = 1e9 + 7;

const ll     INF  = 1e18 + 100;

const int    inf  = 0x3f3f3f3f;

const double pi   = acos(-1.0);

const double eps  = 1e-8;

using namespace std;

int n, m;

int cas, tol, T;

string s, ss;

int main() {

	scanf("%d", &T);

	while(T--) {

		scanf("%d", &n);

		cin >> s;

		int p = -1;

		ll len = s.size();

		int flag = 0;

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

			p++;

			if(!flag)	ss = s.substr(p+1, s.size()-1);

			int t = s[p]-'0';

			ll tlen = len-p-1;

			tlen = (tlen%mod+mod)%mod;

			for(int j=2; j<=t; j++) {

				if(!flag) s += ss;

				if(len + tlen>=n)	flag = 1;

				len = (len+tlen)%mod;

			}

		}

		printf("%lld\n", len);

	}

	return 0;

}

Beingawesomeism

\[Time Limit: 2 s\quad Memory Limit: 256 MB
\]

首先可以发现，只要存在一个 \(A\)，我最多只需要花 \(4\) 步就可以到达最终状态，所以答案一定是 \(0、1、2、3、4、MORTAL\)。

分析一下可以发现:

全为 \(A\)，需要 \(0\) 步
全为 \(P\)，不可能到达
最上/最下行或 最左/最右列全为 \(A\)，需要 \(1\) 步
四个角是 \(A\)，需要 \(2\) 步
中间行或者中间列全为 \(A\)，需要 \(2\) 步
最上/最下行或 最左/最右列有一个 \(A\)，需要 \(3\) 步

暴力讨论每种情况就可以。

view

#include <map>

#include <set>

#include <list>

#include <ctime>

#include <cmath>

#include <stack>

#include <queue>

#include <cfloat>

#include <string>

#include <vector>

#include <cstdio>

#include <bitset>

#include <cstdlib>

#include <cstring>

#include <iostream>

#include <algorithm>

#include <unordered_map>

#define  lowbit(x)  x & (-x)

#define  mes(a, b)  memset(a, b, sizeof a)

#define  fi         first

#define  se         second

#define  pb         push_back

#define  pii        pair<int, int>

#define  INOPEN     freopen("in.txt", "r", stdin)

#define  OUTOPEN    freopen("out.txt", "w", stdout)

typedef unsigned long long int ull;

typedef long long int ll;

const int    maxn = 1e5 + 10;

const int    maxm = 1e5 + 10;

const ll     mod  = 1e9 + 7;

const ll     INF  = 1e18 + 100;

const int    inf  = 0x3f3f3f3f;

const double pi   = acos(-1.0);

const double eps  = 1e-8;

using namespace std;

int n, m;

int cas, tol, T;

char s[70][70];

int solve() {

	int ans = 4;

	if(s[1][1]=='A' || s[1][m]=='A' || s[n][1]=='A' || s[n][m]=='A')	ans = min(ans, 2);

	{

		bool f1 = true, f2 = true, f = false;

		for(int j=1; j<=m; j++) {

			if(s[1][j] == 'P')	f1 = false;

			if(s[n][j] == 'P')	f2 = false;

			if(s[1][j] == 'A')	f = true;

			if(s[n][j] == 'A')	f = true;

		}

		if(f1 || f2)	ans = min(ans, 1);

		bool f3 = true, f4 = true;

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

			if(s[i][1] == 'P')	f3 = false;

			if(s[i][m] == 'P')	f4 = false;

			if(s[i][1] == 'A')	f = true;

			if(s[i][m] == 'A')	f = true;

		}

		if(f3 || f4)	ans = min(ans, 1);

		if(f)	ans = min(ans, 3);

	}

	{

		bool f = true;

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

			for(int j=1; j<=m; j++) {

				if(s[i][j] == 'P')	f = false;

			}

			if(!f)	break;

		}

		if(f)	ans = min(ans, 0);

	}

	{

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

			int cnt = 0;

			for(int j=1; j<=m; j++) {

				cnt += s[i][j]=='A';

			}

			if(cnt == m)	ans = min(ans, 2);

		}

		for(int j=1; j<=m; j++) {

			int cnt = 0;

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

				cnt += s[i][j]=='A';

			}

			if(cnt == n)	ans = min(ans, 2);

		}

	}

	return ans;

}

int main() {

	scanf("%d", &T);

	while(T--) {

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

		int flag = 0;

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

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

			if(flag)	continue;

			for(int j=1; j<=m; j++) {

				if(s[i][j] == 'A')	flag = 1;

			}

		}

		if(flag == 0)	printf("MORTAL\n");

		else	printf("%d\n", solve());

	}

	return 0;

}

Jeremy Bearimy

\[Time Limit: 3 s\quad Memory Limit: 256 MB
\]

思路对了...代码写搓了没写完，我太难了

想要让 \(\sum f(i)\) 最大，那么肯定每次是取最远的两个点做一对。如果想要让其尽量小，那么尽量每次让相邻的两个点做一对，那么我们可以考虑每条边的贡献。

假设有一条连接 \(u\) 和 \(v\) 的边，权值为 \(w\)，那么如果 \(u\) 侧有 \(x\) 个点，\(v\) 侧有 \(y\) 个点

求最大时，我肯定尽量从 \(u\) 侧连一条路到 \(v\) 侧，那么这条边就会被用上 \(min(x, y)\) 次。

求最小时，假如 \(x\) 为偶数，那么 \(y\) 肯定也是偶数，而我又希望让同一对的点靠的尽量近，那么肯定时 \(u\) 侧的点两两凑对，\(v\) 侧的点两两凑对。因为如果我选 \(u\) 和 \(v\) 凑一对，那么两侧都少了一个点，必然要在凑一对，这样多计算了两次 \(w\)，显然亏了。

假如 \(x\) 为奇数，\(y\) 肯定也是奇数，这时候肯定要选一对从 \(u\) 侧到 \(v\) 侧，那么我可以选 \(u\) 和 \(v\) 凑一对，然后两次剩余的又都是偶数，可以各自凑起来。

view

#include <map>

#include <set>

#include <list>

#include <tuple>

#include <ctime>

#include <cmath>

#include <stack>

#include <queue>

#include <cfloat>

#include <string>

#include <vector>

#include <cstdio>

#include <bitset>

#include <cstdlib>

#include <cstring>

#include <iostream>

#include <algorithm>

#include <unordered_map>

#define  lowbit(x)  x & (-x)

#define  mes(a, b)  memset(a, b, sizeof a)

#define  fi         first

#define  se         second

#define  pb         push_back

#define  pii        pair<int, int>

#define  INOPEN     freopen("in.txt", "r", stdin)

#define  OUTOPEN    freopen("out.txt", "w", stdout)

typedef unsigned long long int ull;

typedef long long int ll;

const int    maxn = 2e5 + 10;

const int    maxm = 1e5 + 10;

const ll     mod  = 1e9 + 7;

const ll     INF  = 1e18 + 100;

const int    inf  = 0x3f3f3f3f;

const double pi   = acos(-1.0);

const double eps  = 1e-8;

using namespace std;

int n, m;

int cas, tol, T;

ll ans1, ans2;

vector<pii> g[maxn];

ll sz[maxn];

void dfs(int u, int fa) {

	sz[u] = 1;

	for(auto v : g[u])	if(v.fi != fa) {

		dfs(v.fi, u);

		sz[u] += sz[v.fi];

		if(sz[v.fi]&1)	ans1 += v.se;

		ans2 += min(sz[v.fi], n-sz[v.fi])*v.se;

	}

}

int main() {

	scanf("%d", &T);

	while(T--) {

		int k;

		scanf("%d", &k);

		n = 2*k;

		for(int i=1; i<=n; i++)	g[i].clear();

		for(int i=2, u, v, w; i<=n; i++) {

			scanf("%d%d%d", &u, &v, &w);

			g[u].pb({v, w});

			g[v].pb({u, w});

		}

		ans1 = ans2 = 0;

		dfs(1, 0);

		printf("%lld %lld\n", ans1, ans2);

	}

	return 0;

}

巴特西

Codeforces Round #607 (Div. 2) 题解

Suffix Three

Azamon Web Services

Cut and Paste

Beingawesomeism

Jeremy Bearimy

最新文章

热门文章