A. Do Not Be Distracted!
题意:如果一个字符串中一个字母间断出现,那么老师会怀疑,判断老师是否怀疑。
思路:闭着眼睛敲比速度:)
#include<bits/stdc++.h> using namespace std; int main() { int n,i,j,t; cin>>t; while(t--){ int n; map<char ,int >mo; string s1; cin>>n;cin>>s1; int flag=0; for(i=0;i<n;i++){ if(i!=0){ if(mo[s1[i]]!=0){ if(s1[i-1]==s1[i]){ continue; } else { flag=1; } } } mo[s1[i]]++; } if(flag==1) { scNO; } else { scYES; } } return 0; }
B. Ordinary Numbers
题意:求1-n中有几个数里只有一种数字。
思路:1-10 1 2 3 4 5 6 7 8 9
11-100 11 22 33 44 55 66 77 88 99
然后就继续这么搞,先判断位数,然后再判断当前位大小就行,模拟搞
#include<bits/stdc++.h> using namespace std; int main() { int n,i,j,t; cin>>t; while(t--){ cin>>n; int d1=n,cnt=0; while(d1!=0){ d1/=10; cnt++; } int ans=0; ans+=max(0,cnt-1)*9; for(j=1;j<=9;j++){ int mm=j; for(i=0;i<cnt-1;i++){ mm*=10;mm+=j; } if(n>=mm) ans++; else break; } cout<<ans<<endl; } }
C. Not Adjacent Matrix
题意:给你一个数字n,要求你用n^2个数去建一个正方形边长为n,且一个数上下左右与之相连的数二者差要大于1
思路:不难发现规律其实就是先把奇数列出来再列偶数,然后顺序输出就行比如:
1 3 5
7 9 2
4 6 8
顺便吐槽一下今晚排队那么久,:(导致我最后D过完之后才发现C没过:(
#include<bits/stdc++.h> using namespace std; int a[102][105]; int main() { int n,i,j,t; scanf("%d",&t); while(t--){ scanf("%d",&n); int d1=n*n,m1=-1; int ji=d1%2==0?d1-1:d1; int flag=0,m2=2; int ou=d1%2==0?d1:d1-1; if(n==2){ cout<<-1<<endl; continue; } for(i=1;i<=n;i++){ for(j=1;j<=n;j++){ if(m1==ji) flag=1; if(flag==0){ m1+=2; a[i][j]=m1; } if(flag==1){ a[i][j]=m2; m2+=2; } } } for(i=1;i<=n;i++){ for(j=1;j<=n-1;j++){ cout<<a[i][j]<<" "; } cout<<a[i][j]<<endl; } } }
D. Same Differences
题意:给你一个数组求满足下面条件的有多少对。
思路:把上面的式子转化一下改为aj-j=ai-i,就可以发现其实只要求这个数和它的下标差有多少对,然后求个等差就行.
#include<bits/stdc++.h> using namespace std; #define int long long const int maxn=2e5+1000; struct node { int a,b; }mo[maxn]; signed main() { int t,n,i,j; cin>>t; while(t--){ cin>>n; map<int ,int >m1; for(i=1;i<=n;i++){ cin>>mo[i].a; mo[i].b=i-mo[i].a; m1[mo[i].b]++; } int ans=0; for(i=1;i<=n;i++){ int d1=m1[mo[i].b]; m1[mo[i].b]=0; // cout<<d1<<"*"<<endl; ans+=(d1-1)+((d1-1)*(d1-2))/2; } cout<<ans<<endl; } }
E. Arranging The Sheep
题意:‘*’代表羊,‘.’代表草地,给你一个字符串,要求把所有的羊放在一排
思路:这题思路挺巧妙的,下面的1就是代表羊哈,x就是草地,其实可以发现我要想办法把1并在一起,可以把已经连续的一段1或者连续的一段x合并,而合并其实只有两种情况,一种是从把右边的一段并在左边,一种是把左边的并在右边,可以先从头到尾把每一段合并操作的花费求出来,再倒着求一遍,然后取最小值。
#include<bits/stdc++.h> using namespace std; #define int long long const int maxn=1e6+100; int sum1[maxn]; int sum2[maxn]; signed main() { string s1; int t,i,j,n; cin>>t; while(t--){ cin>>n>>s1; int ans1=0,ans2=0,cnt1=0,cnt2=0,flag=0,cc=0,ccc=0; for(i=0;i<n;i++){ if(s1[i]=='*'){ if(flag==1){ flag=0; ans1+=(cnt1)*cnt2; int dd=cnt1*cnt2; sum1[cc++]=dd; } cnt1++; cnt2=0; } else { if(cnt1>0){ flag=1; } cnt2++; } } reverse(s1.begin(),s1.end()); cnt1=0,cnt2=0,flag=0; for(i=0;i<n;i++){ if(s1[i]=='*'){ if(flag==1){ flag=0; ans2+=(cnt1)*cnt2; int dd=cnt1*cnt2; sum2[ccc++]=dd; } cnt1++; cnt2=0; } else { if(cnt1>0){ flag=1; } cnt2++; } } int ans3=0; for(i=0;i<cc;i++){ ans3+=min(sum1[i],sum2[cc-1-i]); } cout<<ans3<<endl; } return 0; }