Codeforces Round #553 (Div. 2) （A,B,C,D）

分手后的思念是犯贱 2022-02-16 15:53 202阅读 0赞

终测一个题A，B被hack了。好好补题啦

题目链接：[https://codeforces.com/contest/1151][https_codeforces.com_contest_1151]

# [A. Maxim and Biology][] （模拟，不解释） #

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int maxn=110;
    
    int main(){
    	int n;
    	scanf("%d",&n);
    	string s="ACTG",t;
    	cin>>t; 
    	int res=150,sum;
    	for(int i=3;i<n;i++){
    		sum=0;
    		for(int k=0;k<4;k++){
    			int c=abs(t[i-3+k]-s[k]);
    			//printf("c=%d\n",c);
    			c=min(c,26-c);
    			//printf("*c=%d\n",c);
    			sum+=c;
    		}
    		res=min(res,sum);
    	}
    	printf("%d\n",res);
    }

# [B - Dima and a Bad XOR][] （模拟） #

思路：异或和不为0就行，一开始选每一行的第一个数，看看它们的异或结果是不是>0；否则，看能不能换个数，换个之前没有加入过的值，由异或的性质得，异或结果肯定不为0。

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int maxn=510;
    int mp[maxn][maxn],vis[maxn];
    int n,m;
    
    int main(){
    	scanf("%d%d",&n,&m);
    	
    	int res=0;
    	for(int i=1;i<=n;i++){
    		for(int j=1;j<=m;j++){
    			scanf("%d",&mp[i][j]);
    		}
    		res^=mp[i][1];
    		vis[i]=1;
    	}
    	bool flag=false;
    	if(res==0){
    		for(int i=1;i<=n;i++){
    			for(int j=2;j<=m;j++){
    				if(mp[i][j]!=mp[i][1]){
    					vis[i]=j;
    					flag=true;
    					break;
    				}
    			}
    			if(flag) break;
    		}
    	}else flag=true;
    	if(flag){
    		printf("TAK\n");
    		for(int i=1;i<=n;i++){
    			if(i==1) printf("%d",vis[i]);
    			else printf(" %d",vis[i]);
    		}
    		printf("\n");
    	}else{
    		printf("NIE\n");
    	}
    	
    }

# [C - Problem for Nazar][] #

分析：给你一个数的位置pos你可以算出\[1,pos\]区间内奇数和偶数的个数，而奇数是以1为首项，2为等差数列（odd\*odd），偶数以1为首项，2为等差数列(even\*even+even)，由此求出前缀和。剩下的就好求了，sum\[r\]-sum\[l-1\]。ps.记得取模。

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int maxn=510;
    const int MOD=1e9+7;
    
    ll solve(ll id){
    	ll ans=0,L=1,odd=0,even=0,tmp;
    	int flag=1;
    	while(id>0){
    		tmp=min(L,id);
    		if(flag) odd+=tmp;
    		else even+=tmp;
    		id-=tmp;
    		L*=2;
    		flag^=1;
    	}
    	odd%=MOD;
    	even%=MOD;
    	//cout<<"sumodd="<<(odd*odd)%MOD<<endl;
    	//cout<<"sumeven="<<(even*even)%MOD<<endl;
    	ans=((odd*odd)%MOD+((even*even)%MOD+even)%MOD)%MOD;
    	//cout<<"ans="<<ans<<endl;
    	return ans;
    }
    
    
    int main(){
    	ll l,r;
    	scanf("%lld%lld",&l,&r);
    	ll a=solve(r),b=solve(l-1);
    	//cout<<"a="<<a<<",b="<<b<<",a-b="<<(a-b+MOD)%MOD<<endl;
    	printf("%lld\n",(a-b+MOD)%MOD);  //因为a,b为取模后的结果，大小关系不确定，所以加上MOD保证结果为正
    	return 0;
    }

# [D - Stas and the Queue at the Buffet][] #

分析：a⋅(j−1)+b⋅(n−j) ，即(a-b)\*j-a+n\*b从该式可以得出（a-b）越大的应该尽可能往左边坐，这样不满值才能更小。ps.我怎么记得比赛的时候就分析出这题了呢？！怎么没写

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int maxn=1e5+10;
    const int MOD=1e9+7;
    
    struct Node{
    	ll a,b;
    	ll dif;
    	bool operator <(const Node &A)const{
    		return dif>A.dif;
    	}
    }mes[maxn]; 
    
    
    int main(){
    	int n;
    	scanf("%d",&n);
    	for(int i=1;i<=n;i++){
    		scanf("%lld%lld",&mes[i].a,&mes[i].b);
    		mes[i].dif=mes[i].a-mes[i].b;
    	}
    	sort(mes+1,mes+1+n);
    	ll ans=0;
    	for(int i=1;i<=n;i++){
    		//ans+=mes[i].dif*i-mes[i].a+n*mes[i].b;
    		ans+=(i-1)*mes[i].a+(n-i)*mes[i].b;
    	}
    	printf("%lld\n",ans);
    	return 0;
    }

[https_codeforces.com_contest_1151]: https://codeforces.com/contest/1151
[A. Maxim and Biology]: https://codeforces.com/contest/1151/problem/A
[B - Dima and a Bad XOR]: https://codeforces.com/contest/1151/problem/B
[C - Problem for Nazar]: https://codeforces.com/contest/1151/problem/C
[D - Stas and the Queue at the Buffet]: https://codeforces.com/contest/1151/problem/D