Educational Codeforces Round 65 (Rated for Div. 2) A,B,C,D

初めてインタラクティブな問題を書いて、幸いにも大神の指導を得て、さもなくばこの試合は本当に多くの点を得ました.
A. Telephone Number
トランスファゲート
最初の8の後ろの数字の個数が11以上であればよい

#include 
using namespace std;
const int maxn = 3e5 + 10;
char s[maxn];
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n;
        scanf("%d",&n);
        string s;
        cin >> s;
        int i;
        for(i = 0;i < n; i++)
        {
            if(s[i] == '8')
                break;
        }
        if(n - i >= 11)
            printf("YES
");
        else
            printf("NO
");
    }
    return 0;
}

B. Lost Numbers
インタラクティブな問題は、6つの数字をあげて、4回の質問でこの6つの数字の配列を確定させます.

#include
using namespace std;
int a[6] = {4, 8, 15, 16, 23, 42},ans[5];
int main()
{
#ifndef ONLINE_JUDGE
    freopen("in","r",stdin);
#endif
    for(int i = 1; i <= 4; i++)
    {
        printf("? %d %d
", i, i + 1);
        fflush(stdout);
        scanf("%d",&ans[i]);
    }
    while(next_permutation(a, a+6))
    {
        if(a[1] * a[0] == ans[1] && a[2] * a[1] == ans[2] && a[3] * a[2] == ans[3] && a[4] * a[3] == ans[4])
            break;
    }
    cout << "!";
    for(int i = 0; i < 6; i++)
        printf(" %d", a[i]);
    cout << "
";
    return 0;
}

C. News Distribution
トランスファゲート
単純な集計です.集計時に現在のノードが存在する集合のノード数を記録するために配列を維持する必要があります.

#include
using namespace std;
const int maxn = 5e5+10;
int pre[maxn],x[maxn],ans[maxn];
int Find(int x)
{
    if (x != pre[x])
        pre[x] = Find(pre[x]);
    return pre[x];
}
void combine(int a, int b)
{
    int fa = Find(a);
    int fb = Find(b);
    if (fa == fb)
        return;
    pre[fb] = fa;
    ans[fa] += ans[fb];
}
int main()
{
    int n,m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        pre[i] = i;
        ans[i] = 1;
    }
    int a;
    for (int j = 0; j < m; j++)
    {
        cin >> a;
        for (int i = 0; i < a; i++)
        {
            cin >> x[i];
            if (i >= 1)
                combine(x[i - 1], x[i]);
        }
    }
    for (int i = 1; i <= n; i++)
        cout << ans[Find(i)] << " ";
    return 0;
}

D. Bicolored RBS
トランスファゲート
タイトルは2つの括弧の深さの差をできるだけ小さくして、先に走って最大の深さを求めて、それから深さは半分に分けて、半分は1種で、もう半分はもう1種です.

#include
using namespace std;
typedef long long ll;
const int maxn = 2e5+10;
int mp[maxn];
string s;
int main()
{
	#ifndef ONLINE_JUDGE
	freopen("in.txt","r",stdin);
	#endif
	int n;
	cin >> n >> s;
	int tmp = 0,ans = 0;
	for(int i = 0;i < n; i++)
	{
		if(s[i] == '(')
		{
			tmp++;
			mp[i] = tmp;
		}	
		else
		{
			mp[i] = tmp;
			tmp--;
		}	
		ans = max(ans,tmp);
	}
	ans = ans / 2;
	for(int i = 0;i < n; i++)
	{
		if(mp[i] > ans)
			printf("1");
		else
			printf("0");
	}
	printf("
");
	return 0;
}