Educational Codeforces Round 72 (Rated for Div. 2)

A - Creating a Character

求出第一个数字的可能的最大值和最小值，减一下就是答案

#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
int main()
{
	int t;
	sc("%d", &t);
	while (t--)
	{
		ll a, b, c;
		sc("%lld%lld%lld", &a, &b, &c);
		if (a + c <= b)
		{
			pr("0\n");
		}
		else
		{
			ll maxn = a + c;
			ll minn = (a + b + c) / 2 + 1;
			minn = max(minn, a);
			ll cnt = maxn - minn + 1;
			pr("%d\n", cnt);
		}
	}
}

B - Zmei Gorynich

去一个能打掉最多的，作为最后打的，然后取一个能打掉的绝对值最多的，作为中间的，然后直接除一下判断需要多少个中间的就可以

#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
int a[105][2];
int main() 
{
	int T;
	sc("%d", &T);
	while (T--) 
	{
		int n, x;
		sc("%d%d", &n, &x);
		int q, w, f = -1e9 - 7, maxn = 0;
		for (int i = 0; i < n; i++)
		{
			sc("%d%d", &a[i][0], &a[i][1]);
			if (f < a[i][0] - a[i][1])
			{
				f = a[i][0] - a[i][1];
				q = a[i][0], w = a[i][1];
			}
			maxn = max(maxn, a[i][0]);
		}
		if (f <= 0)
		{
			if (x <= maxn)
			{
				pr("1\n");
				goto qwe;
			}
			else
			{
				pr("-1\n");
				goto qwe;
			}
		}
		else
		{
			if (x <= maxn)
			{
				pr("1\n");
				goto qwe;
			}
			else
			{
				ll ans = ceil(1.0 * (x - maxn) / f);
				pr("%lld\n", ans + 1);
			}
		}
		qwe:;
	}
}

C - The Number Of Good Substrings

找到所有1的位置，以这个位置为起始，判断后面每加入一位数字，前面需要零的个数，如果零的数量不够，就跳出，否则算一个贡献。

#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
char s[200005];
int main()
{
	int T;
	sc("%d", &T);
	while (T--)
	{
		sc("%s", s);
		int len = strlen(s);
		ll ans = 0, tot = 0;
		for (int i = 0; i < len; i++)
		{
			if (s[i] == '0')
				tot++;
			else
			{
				int sum = 0;
				for (int j = i; j < len; j++)
				{
					sum = sum * 2 + s[j] - '0';
					if (j - i + 1 <= sum && sum <= j - i + 1 + tot)
					{
						ans++;
					}
					else if (sum > j - i + 1 + tot)
						break;
				}
				tot = 0;
			}
		}
		pr("%lld\n", ans);
	}
}

D - Coloring Edges

有向图，给每个图一个颜色，要求相同颜色的边不能连成一个环，求需要的最少颜色。

如果有环，那么答案一定是2，否则答案是1。

dfs判环

#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
const int MAXN = 5005;
struct edge
{
	int to;
	int nex;
}e[MAXN];
int head[MAXN], tot;
void init()
{
	memset(head, -1, sizeof(head));
	tot = 1;
}
void add(int a, int b)
{
	e[tot] = edge{ b,head[a] };
	head[a] = tot++;
}
bool cnt[MAXN];
int ans[MAXN];
bool vis[MAXN];
bool flag;
void dfs(int u)
{
	if (flag) 
		return;
	for (int i = head[u]; i + 1; i = e[i].nex)
	{
		int to = e[i].to;
		if (cnt[to] == true)//如果走到了走过的点
		{
			flag = true;
			return;
		}
		cnt[to] = true;
		if (!vis[to])//只dfs没有走过的点
		{
			vis[to] = true;
			dfs(to);
		}
		cnt[to] = false;
	}
}
int main()
{
	init();
	int n, m;
	sc("%d%d", &n, &m);
	for (int i = 0; i < m; i++)
	{
		int a, b;
		sc("%d%d", &a, &b);
		add(a, b);
		ans[i] = (a > b ? 2 : 1);
	}
	for (int i = 1; i <= n; i++)
	{
		if (vis[i] == false)
		{
			vis[i] = true;
			cnt[i] = true;//标记走过
			dfs(i);
			cnt[i] = false;//取消标记
		}
	}
	if (flag)
	{
		pr("2\n");
		for (int i = 0; i < m; i++)
			pr("%d%c", ans[i], i == m - 1 ? '\n' : ' ');
	}
	else
	{
		pr("1\n");
		for (int i = 0; i < m; i++)
			pr("1%c", i == m - 1 ? '\n' : ' ');
	}
}