思路：水，直接判断相等不相等；
#include<bits/stdc++.h> using namespace std; #define ll long long #define pi (4*atan(1.0)) #define eps 1e-7 const int N=1e5+10,M=1e6+10,inf=2147483647; const ll INF=1e18+10,mod=2147493647; char a[N],b[N]; int main() { scanf("%s%s",a,b); int x=strlen(a); for(int i=0;i<x;i++) { printf("%d",(a[i]!=b[i]?1:0)); } return 0; }
After the contest in comparing numbers, Shapur's teacher found out that he is a real genius and that no one could possibly do the calculations faster than him even using a super computer!
Some days before the contest, the teacher took a very simple-looking exam and all his n students took part in the exam. The teacher gave them 3 strings and asked them to concatenate them. Concatenating strings means to put them in some arbitrary order one after the other. For example from concatenating Alireza and Amir we can get to AlirezaAmir or AmirAlireza depending on the order of concatenation.
Unfortunately enough, the teacher forgot to ask students to concatenate their strings in a pre-defined order so each student did it the way he/she liked.
Now the teacher knows that Shapur is such a fast-calculating genius boy and asks him to correct the students' papers.
Shapur is not good at doing such a time-taking task. He rather likes to finish up with it as soon as possible and take his time to solve 3-SAT in polynomial time. Moreover, the teacher has given some advice that Shapur has to follow. Here's what the teacher said:
- As I expect you know, the strings I gave to my students (including you) contained only lowercase and uppercase Persian Mikhi-Script letters. These letters are too much like Latin letters, so to make your task much harder I converted all the initial strings and all of the students' answers to Latin.
- As latin alphabet has much less characters than Mikhi-Script, I added three odd-looking characters to the answers, these include "-", ";" and "_". These characters are my own invention of course! And I call them Signs.
- The length of all initial strings was less than or equal to 100 and the lengths of my students' answers are less than or equal to 600
- My son, not all students are genius as you are. It is quite possible that they make minor mistakes changing case of some characters. For example they may write ALiReZaAmIR instead of AlirezaAmir. Don't be picky and ignore these mistakes.
- Those signs which I previously talked to you about are not important. You can ignore them, since many students are in the mood for adding extra signs or forgetting about a sign. So something like Iran;;-- is the same as --;IRAN
- You should indicate for any of my students if his answer was right or wrong. Do this by writing "WA" for Wrong answer or "ACC" for a correct answer.
- I should remind you that none of the strings (initial strings or answers) are empty.
- Finally, do these as soon as possible. You have less than 2 hours to complete this.
The first three lines contain a string each. These are the initial strings. They consists only of lowercase and uppercase Latin letters and signs ("-", ";" and "_"). All the initial strings have length from 1 to 100, inclusively.
In the fourth line there is a single integer n (0 ≤ n ≤ 1000), the number of students.
Next n lines contain a student's answer each. It is guaranteed that the answer meets what the teacher said. Each answer iconsists only of lowercase and uppercase Latin letters and signs ("-", ";" and "_"). Length is from 1 to 600, inclusively.
For each student write in a different line. Print "WA" if his answer is wrong or "ACC" if his answer is OK.
Iran_
Persian;
W_o;n;d;e;r;f;u;l;
7
WonderfulPersianIran
wonderful_PersIAN_IRAN;;_
WONDERFUL___IRAN__PERSIAN__;;
Ira__Persiann__Wonderful
Wonder;;fulPersian___;I;r;a;n;
__________IranPersianWonderful__________
PersianIran_is_Wonderful
ACC
ACC
ACC
WA
ACC
ACC
WA
Shapur;;
is___
a_genius
3
Shapur__a_is___geniUs
is___shapur___a__Genius;
Shapur;;is;;a;;geni;;us;;
WA
ACC
ACC
题意：不区分大小写跟符号，问能否由三个字符串拼接成，可以输出ACC，否则WA；
思路：字符串模拟；
#include<bits/stdc++.h> using namespace std; #define ll long long #define pi (4*atan(1.0)) #define eps 1e-7 const int N=1e5+10,M=1e6+10,inf=2147483647; const ll INF=1e18+10,mod=2147493647; string a[5]; char str[5][N]; map<string,int>ans; int main() { for(int i=0;i<3;i++) scanf("%s",&str[i]); for(int i=0;i<3;i++) { int len=strlen(str[i]); for(int j=0;j<len;j++) { if(str[i][j]>='a'&&str[i][j]<='z') a[i]+=str[i][j]; if(str[i][j]>='A'&&str[i][j]<='Z') a[i]+=str[i][j]-'A'+'a'; } } ans[a[0]]=1; ans[a[1]]=1; ans[a[2]]=1; ans[a[0]+a[1]]=1; ans[a[1]+a[0]]=1; ans[a[0]+a[2]]=1; ans[a[2]+a[0]]=1; ans[a[1]+a[2]]=1; ans[a[2]+a[1]]=1; ans[a[0]+a[1]+a[2]]=1; ans[a[0]+a[2]+a[1]]=1; ans[a[1]+a[0]+a[2]]=1; ans[a[1]+a[2]+a[0]]=1; ans[a[2]+a[0]+a[1]]=1; ans[a[2]+a[1]+a[0]]=1; int q; scanf("%d",&q); while(q--) { string k=""; scanf("%s",str[4]); int len=strlen(str[4]); for(int i=0;i<len;i++) { if(str[4][i]>='a'&&str[4][i]<='z') k+=str[4][i]; if(str[4][i]>='A'&&str[4][i]<='Z') k+=str[4][i]-'A'+'a'; } if(ans[k]) printf("ACC "); else printf("WA "); } return 0; }
题意：进制转换，a为当前数的进制数，转化为b，R为罗马数字；
思路：模拟；
#include<bits/stdc++.h> using namespace std; #define ll long long #define pi (4*atan(1.0)) #define eps 1e-14 #define bug(x) cout<<"bug"<<x<<endl; const int N=2e5+10,M=1e6+10,inf=1e9+10; const ll INF=1e18+10,mod=2147493647; char b[10]; char num[N]; ll c(char a) { if(a>='A'&&a<='Z') return a-'A'+10; return a-'0'; } char c2(ll x) { if(x<10) return x+'0'; return x-10+'A'; } string ans; int main() { ll a; scanf("%lld%s",&a,b); scanf("%s",num); ll base=1,p=0; int x=strlen(num); for(int i=x-1;i>=0;i--,base*=a) p+=c(num[i])*base; if(b[0]=='R') { int n4=p/1000; p%=1000; int n3=p/100; p%=100; int n2=p/10; int n1=p%10; for(int i=0;i<n4;i++) ans+='M'; if(n3==9) ans+="CM"; else if(n3==4) ans+="CD"; else if(n3>=5) ans+="D"; if(n3%5!=4) for(int i=0;i<n3%5;i++) ans+='C'; if(n2==9) ans+="XC"; else if(n2==4) ans+="XL"; else if(n2>=5) ans+="L"; if(n2%5!=4) for(int i=0;i<n2%5;i++) ans+='X'; if(n1==9) ans+="IX"; else if(n1==4) ans+="IV"; else if(n1>=5) ans+="V"; if(n1%5!=4) for(int i=0;i<n1%5;i++) ans+='I'; cout<<ans<<endl; } else { int q=0; for(int i=strlen(b)-1,j=1;i>=0;i--,j*=10) q+=c(b[i])*j; while(p) { ans+=c2(p%q); p/=q; } reverse(ans.begin(),ans.end()); cout<<ans<<endl; if(ans.size()==0) cout<<0<<endl; } return 0; }
题意：给你一棵树，n个节点，1为根遍历这颗树走的最小的权值；
思路：总权值*2-max一条链；
#include<bits/stdc++.h> using namespace std; #define ll long long #define pi (4*atan(1.0)) #define eps 1e-7 const int N=1e5+10,M=1e6+10,inf=2147483647; const ll INF=1e18+10,mod=2147493647; struct is { int v,w,nex; }edge[N<<1]; int head[N<<1],edg; ll ans,maxx; void init() { memset(head,-1,sizeof(head)); ans=maxx=edg=0; } void add(int u,int v,int w) { edg++; edge[edg].v=v; edge[edg].w=w; edge[edg].nex=head[u]; head[u]=edg; } void dfs(int x,int fa,ll val) { //cout<<x<<endl; maxx=max(maxx,val); for(int i=head[x];i!=-1;i=edge[i].nex) { int v=edge[i].v; int w=edge[i].w; if(v==fa)continue; dfs(v,x,val+w); } } int main() { init(); int n; scanf("%d",&n); for(int i=1;i<n;i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); add(u,v,w); add(v,u,w); ans+=w; } dfs(1,-1,0); cout<<ans*2-maxx<<endl; return 0; } /* 3 1 2 3 2 3 3 */
题意：找三元组；
思路：枚举中点，找前面比其大的个数x，后面比其小的个数y，贡献就为x*y；
树状数组+离散化即可；
#include<bits/stdc++.h> using namespace std; #define ll long long #define pi (4*atan(1.0)) #define eps 1e-7 const int N=1e5+10,M=1e6+10,inf=2147483647; const ll INF=1e18+10,mod=2147493647; int tree[M]; int lowbit(int x) { return x&-x; } void update(int x,int c) { while(x<M) { tree[x]+=c; x+=lowbit(x); } } int query(int x) { int sum=0; while(x) { sum+=tree[x]; x-=lowbit(x); } return sum; } int s[M],a[M],len; ll pre[M],nex[M]; int getnum(int x) { int pos=lower_bound(s+1,s+1+len,x)-s; return pos; } int main() { int n; scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); s[i]=a[i]; } sort(s+1,s+n+1); len=unique(s+1,s+1+n)-s-1; for(int i=1;i<=n;i++) a[i]=getnum(a[i]); for(int i=1;i<=n;i++) { update(a[i],1); pre[i]=query(M-2)-query(a[i]); } memset(tree,0,sizeof(tree)); for(int i=n;i>=1;i--) { update(a[i],1); nex[i]=query(a[i]-1); } ll ans=0; for(int i=1;i<=n;i++) { ans+=nex[i]*pre[i]; } cout<<ans<<endl; return 0; }