Educational Codeforces Round 68 (Rated for Div. 2)补题

A. Remove a Progression

签到题，易知删去的为奇数，剩下的是正偶数数列。

#include<iostream>

using namespace std;

int T;

int n,x;

int main(){

	cin>>T;

	while(T--){

		cin>>n>>x;

		cout<<x * 2<<endl;

	}

	return 0;

}

B. Yet Another Crosses Problem

n*m存在上界，以一维数组储存二维数组。统计各个行（列）的白块数量，找出其中数量最少的行（列）（注：不一定只有一行（列）的白块最少）。输出结果为最小行数与最小列数之和。

仍遍历满足上述条件的行和列的交点，若其为白块，则输出结果需减去重复点。

#include<iostream>

#include<algorithm>

using namespace std;

const int L = 400000+500;

int q,n,m;

char M[L];

int ans;

int NN[L],NM[L];

int f(){

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

	for(int i = 0;i<m;++i) NM[i] = 0;

	for(int i = 0;i<n;++i)

		for(int j = 0;j<m;++j)

			if(M[i*m+j] == '.') NN[i]++;

	for(int j = 0;j<m;++j)

		for(int i = 0;i<n;++i)

			if(M[i*m+j] == '.') NM[j]++;

	int minn = NN[0];

	int minm = NM[0];

	for(int i =0;i<n;++i) minn = min(minn,NN[i]);

	for(int i =0;i<m;++i) minm = min(minm,NM[i]);

	int ans = minn + minm;

	for(int i = 0;i<n;++i)

		for(int j = 0;j<m;++j)

			if(NN[i] == minn&&NM[j] == minm)

				if(M[i*m+j] == '.') return ans-1;

	return ans;

}

int main(){

	cin>>q;

	while(q--){

		cin>>n>>m;

		for(int i =0;i<n;++i)

			cin>>(M + i*m);

		ans = f();

		cout<<ans<<endl;

	}

	return 0;

}

C. From S To T

通过判断串s 是否由串t 退化而来，初步确定答案。

之后判断串t 删去与串s 对应的字符后是否可以由串p 的元素所构成。

#include<iostream>

#include<algorithm>

#include<cstring>

#include<queue>

using namespace std;

const int L = +;

int q;

char s[L],t[L],p[L];

int T[L];

int al[];

int main(){

    cin>>q;

    while(q--){

        cin>>s>>t>>p;

        bool ans = true;

        for(int i =;i<;++i) al[i] = ;

        for(int i =;i<L;++i) T[i] = ;

        for(int i =;p[i]!='\0';++i)

            al[p[i] - 'a']++;

        int pj = ;

        bool flag = false;

        for(int i = ;s[i]!='\0';++i){

            flag = false;

            for(int j = pj;j<strlen(t);++j){

                if(s[i] == t[j]){

                    T[j] = ;

                    flag = true;

                    pj = j+;

                    break;

                }

            }

            if(!flag){

                ans = false;

                break;

            }

        }

        if(!ans){

            cout<<"NO"<<endl;

            continue;

        }

        for(int i = strlen(t);i>=;--i){

            if(T[i] == ){

                for(int j = i;t[j]!='\0';++j)

                    t[j] = t[j+];

            }

        }

        for(int i = ;t[i]!='\0';++i){

            if(al[t[i] - 'a'] > ){

                al[t[i] - 'a']--;

            }

            else{

                ans = false;

                break;

            }

        }

        if(ans)

            cout<<"YES"<<endl;

        else

            cout<<"NO"<<endl;

    }

    return ;

}

D. 1-2-K Game

博弈，找规律。情况可分为

①n < k

②n>=k 且 k%3=0

③n>=k 且 k%3≠0

对情况①③，若n%3=0先手必败，反之必胜。

对情况② 令 n = n%(k+1) 条件一：若n =k，先手必胜；条件二：若n%3==0，先手必败，反之必胜。条件一优先级高于条件二。

#include<iostream>

using namespace std;

int T;

int n,k;

int main(){

    cin>>T;

    while(T--){

        cin>>n>>k;

        if( n < k ){

            n%=;

            if(n == ) cout<<"Bob"<<endl;

            else cout<<"Alice"<<endl;

        }

        else{

            if(k % == ){

                n %= k + ;

                if(n == k)

                    cout<<"Alice"<<endl;

                else{

                    n%=;

                    if(n == ) cout<<"Bob"<<endl;

                    else cout<<"Alice"<<endl;

                }

            }

            else{

                n%=;

                if(n == ) cout<<"Bob"<<endl;

                else cout<<"Alice"<<endl;

            }

        }

    }

    return ;

}

巴特西

Educational Codeforces Round 68 (Rated for Div. 2)补题

最新文章

热门文章