Hello sir.

This is muy solution to 1702B.

We can travel though the hole string, and use $$$ans$$$ to add up the sum of the days, and use $$$tot$$$ to add up how many letters Polycarp has remembered today.

Another array $$$rem_x$$$ is used to mark if the letter is remebered.

When $$$tot == 3$$$, this means he should use at least one more day, so we can ++ans.

When a new letter is remembered today, he don't have to remember it again, otherwise, ++tot.

Note that: please remember to clear $$$rem$$$ when '++ans'.

My code:

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
inline int read()
{
	bool flag = true;
	char c = getchar();
	if (c == '-') flag = false;
	while(!(c >= '0' && c <= '9')) c = getchar();
	int x = 0;
	while(c >= '0' && c <= '9')
	{
		x = x * 10 + c - '0';
		c = getchar();
	}
	if (flag == true) return x;
	return -x;
}
bool rem[27];
int main()
{
	int t = read();
	while (t--)
	{
		string s;
		cin >> s;
		int ans = 1, tot = 0;
		memset(rem, 0, sizeof(rem));
		for (int i = 0; i < s.size(); ++i)
		{
			if (rem[s[i] - 'a'] == 1) continue;
			if (tot == 3)
			{
				memset(rem, 0, sizeof(rem));
				++ans;
				tot = 0;
			}
			++tot;
			rem[s[i] - 'a'] = 1;
		}
		printf("%d\n", ans);
	}
	return 0;
}

Yes, you are right, I made a lot of mistake on $$$int$$$ and $$$long \ long$$$.

In a contest, you can try this:

#define int long long
……
signed main()
{


}

**** And when you use printf to output, don't forget to use "%lld" instead of "%d".

In my opinion, after serveral operations, the number of the sum of $$$01$$$ and $$$10$$$ will not change.

The problem says that $$$s_{i - 1} != s_{i + 1}$$$, for example, "100" will change to "110", and "001" will change to "011".

We can find that the count of differences of the adjoining numbers will not change.

In fact, XOR can find that if the adjoining numbers is not same, because $$$0 \ XOR\ 1 = 1$$$, $$$1 \ XOR \ 0 = 1$$$, $$$0 \ XOR \ 0 = 0$$$, $$$1 \ XOR \ 1 = 1$$$.

I hope this solution can help you.

I wonder that why I fail to hack to this code.

link

int a[110]; The size of the array is only $$$110$$$, but when $$$n = 100$$$, and there will be $$$200$$$ numbers, why it will not get WA / RE?

Can anyone tell me, thanks a lot.

Note that, in problem G, don't use memset all the times, or you will get TLE on test 2 (I had tried it), because memset has a time complexity as $$$O(n \times \log a_i)$$$, if $$$t$$$ is very big, the total time complexity will be too large to solve this problem.

I hope that this note will help you!

Sorry, it's my mistake. Let me show you my code of problem E.

# include <bits/stdc++.h>
#define ll long long
#define re register
#define il inline
using namespace std;
char g[110][110];
int f[110][110];
int cnt[5];
int main()
{
//	freopen("output.out", "w", stdout);
	int t;
	scanf("%d", &t);
	while (t--)
	{
		int n, ans = 0;
		scanf("%d", &n);
		for (int i = 1; i <= n; ++i)
		{
			string s;
			cin >> s;
			for (int j = 1; j <= n; ++j)
				g[i][j] = int(s[j - 1] - '0');
		}
		int len = (n + 1) >> 1;
		for (int i = 1; i <= len; ++i)
		{
			int k;
			if (n % 2) k = len - 1;
			else k = len;
			for (int j = 1; j <= k; ++j)
			{
				cnt[0] = cnt[1] = 0;
				int x = n - i + 1, y = n - j + 1;
				cnt[g[i][j]]++;
				cnt[g[j][x]]++;
				cnt[g[y][i]]++;
				cnt[g[x][y]]++;
			//	printf("%d %d %d %d\n", i, j, cnt[0], cnt[1]);
				ans += min(4 - cnt[0], cnt[0]);
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}

Hello sir, There are two layers of recurrence in your code, so your code's time complexity is $$$O(n^2)$$$, and when $$$n = 200000$$$,you will get TLE.

I solved this problem with set, and my time complexity is $$$o(n \log n)$$$.

This is my code:

# include <bits/stdc++.h>
#define ll long long
#define re register
#define il inline
using namespace std;
string s[100010];
int main()
{
	int t;
	scanf("%d", &t);
	while (t--)
	{
		int n; bool f = 0;
		scanf("%d", &n);
		set <string> str;
		for (int i = 1; i <= n; ++i)
		{
			cin >> s[i];
			str.insert(s[i]);
		}
		for (int i = 1; i <= n; ++i)
		{
			f = 0;
			for (int j = 1; j < s[i].size(); ++j)
			{
				string a = s[i].substr(0, j), b = s[i].substr(j, s[i].size());
				if (str.find(a) != str.end() && str.find(b) != str.end())
				{
					printf("1");
					f = 1;
					break;
				}
			}
			if (f == 0) printf("0");
		}
		printf("\n");
	}
	return 0;
}

Although there are two lawers of recurrence in my code, but $$$s[i].size \le 8$$$, so my code doesn't go TLE.

I think this contest is quiet interesting, but in my opinion, there are two drawbacks.

First, it is easier than other div.2, like problem C and D, they are a little bit easy.

Secound, why both problem C and D are all binary search. It's kind of repeated.

In my opinion, you can solve the problem in this way.

Use an integer $$$a$$$ to save the minium number of operations to "cut" the trees in the same height . Consider that when you meet a "new" tree which has a height of $$$h$$$. There are two conditions.

• If $$$h \le a$$$, you have to decrease the height of all the "old" trees to $$$h$$$( use $$$a - h$$$ operations), and change the value of $$$a$$$ to $$$h$$$.
• Otherwise you only have to decrease the height of the "new" trees $$$h - a$$$ times, and you don't have to change the value of $$$a$$$

We can find that in both situations, you have to operate $$$|h - a|$$$ times (This is the reason to add $$$|h - a|$$$ to the answer, $$$|h - a|$$$ is the $$$x$$$ in the official solution.

In the end, you should add |a| operations to decrease / increase all the height to 0.

This is my code:161360992

Thanks to user AAK who told me this method.

I'm sorry that I am not good at using English to write articals. I hope this message will help you.

Thank you very much. Your solution is very helpful to me.

Exuse me, may I ask a question?

Does $$$curh$$$ mean the final leval that is equal all the height of the trees