A. Salem and Sticks（暴力）
题意：给你n个棒子，长度分别为ai，让你找到一个长度x，使得n个棒子的长度都变为x+1或者x-1或者x的花费最小，花费为abs(ai-b);
解：因为n只有1000，棒子最长也只有100；所以在1-100内暴力就行了；
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=1e5+10; const int inf=0x3f3f3f3f; int a[maxn]; int b[maxn],n,c[maxn]; int gao(int ans){ int sum=0; for(int i=1;i<=n;i++){ if(a[i]==ans+1||a[i]==ans||a[i]==ans-1)continue; sum+=abs(ans-a[i])-1; } return sum; } int main(){ cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; } sort(a+1,a+1+n); int flag=0,sum1=0,sum2=0,sum3=0,minn=inf; for(int i=1;i<=n;i++){ if(a[i]==a[i-1]) continue; sum1=gao(a[i]); sum2=gao(a[i]-1); sum3=gao(a[i]+1); minn=min(minn,min(sum1,min(sum2,sum3))); if(minn==sum1){ flag=a[i]; } else if(minn==sum2){ flag=a[i]-1; } else if(minn==sum3){ flag=a[i]+1; } } cout<<flag<<‘ ‘<<minn<<endl; return 0; }View Code
B. Zuhair and Strings
题意：给你一个字符串s，问你有多少个长度为k的连续相同的字符字串；
解：统计每个字母长度为k的字串用num记录，然后跑一遍num找出最大值；刚开始忘了处理结尾的字符导致wa了两罚；
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=2e5+10; const int inf=0x3f3f3f3f; int num[30]; int main(){ ios::sync_with_stdio(false); string s; int n,k; cin>>n>>k; cin>>s; int cnt=1; for(int i=1;i<n;i++){ if(s[i]==s[i-1]){ cnt++; } else{ if(cnt/k)num[s[i-1]-‘a‘]+=cnt/k; cnt=1; } } if(cnt/k)num[s[n-1]-‘a‘]+=cnt/k; int ans=0; for(int i=0;i<26;i++){ ans=max(ans,num[i]); } cout<<ans<<endl; return 0; }View Code
C. Ayoub and Lost Array（DP）
题意：问区间[L,R]内n个数之和%3==0有多少组，数字可以重复使用；
解：刚开始想用多重集排列来做，先求出总的，然后再减去%3==1 %3==2的个数，算了半天发现走不通；
然后观摩了别人的做法，dp
先算一下L-R内%3分别等于0，1，2的个数
用前缀的思想，L-R内%3==0的有R/3-(L-1)/3；那么1和2分别就是(R+2)/3-(L+1)/3 (R+1)/3-(L)/3 (这个可以用a%3=0然后再推一下)
dp[i][0,1,2] i表示选择 i 个时的情况%3==0/1/2的分别有几种
然后dp[i][0]=dp[i-1][0]*a+dp[i-1][1]*c+dp[i-1][2]*b;
其他两个也跟上面差不多；
#include <bits/stdc++.h> using namespace std; const int maxn=2e5+10; const int mod=1e9+7; typedef long long ll; ll dp[maxn][3]; int main(){ ll n,l,r; cin>>n>>l>>r; ll a=r/3-(l-1)/3; ll b=(r+2)/3-(l+1)/3; ll c=(r+1)/3-l/3; dp[1][0]=a,dp[1][1]=b,dp[1][2]=c; for(int i=2;i<=n;i++){ dp[i][0]=(dp[i-1][0]*a%mod+dp[i-1][1]*c%mod+dp[i-1][2]*b%mod)%mod; dp[i][1]=(dp[i-1][1]*a%mod+dp[i-1][0]*b%mod+dp[i-1][2]*c%mod)%mod; dp[i][2]=(dp[i-1][2]*a%mod+dp[i-1][0]*c%mod+dp[i-1][1]*b%mod)%mod; } cout<<dp[n][0]%mod<<endl; return 0; }View Code
D. Kilani and the Game（感觉比c简单）（BFS）
题意：给你n*m的图，有p个人，每个人的扩展速度为si，然后#不能扩展，每轮每个人只能扩展一次，直到扩展到不能扩展为止，问每个人的领域是多少
解：每轮每个人跑si次BFS，每次跑完的点再用一个queue来存，然后跑完当前所有的，再把暂存的放到原本的队列中
没做到完美的剪枝导致T了2发；
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=1e3+10; int n,m,p; char s[maxn]; ll ans[maxn]; bool vis[maxn][maxn]; ll sp[maxn]; int cnt=0; int dx[4]={0,1,-1,0}; int dy[4]={1,0,0,-1}; queue<pair<int,int>>que[maxn],t; void bfs(int st){ int o=sp[st]; int tot=0; while(tot<o){ int xx=cnt; while(!que[st].empty()){ pair<int,int>u=que[st].front();que[st].pop(); int x=u.first; int y=u.second; for(int i=0;i<4;i++){ int nx=x+dx[i]; int ny=y+dy[i]; if(nx<0||ny<0||nx>=n||ny>=m||vis[nx][ny])continue; vis[nx][ny]=true; t.push(make_pair(nx,ny)); ans[st]++; cnt++; } } if(xx==cnt)return;//剪枝（这个很重要） if(cnt>=n*m)return; while(!t.empty()){ pair<int,int>u=t.front(); t.pop(); que[st].push(u); } tot++; if(o==tot)return; } } int main(){ ios::sync_with_stdio(false); cin>>n>>m>>p; for(int i=1;i<=p;i++){ cin>>sp[i]; } for(int i=0;i<n;i++){ cin>>s; for(int j=0;j<m;j++){ if(s[j]==‘#‘){ vis[i][j]=true; cnt++; } else if(s[j]>=‘0‘&&s[j]<=‘9‘){ vis[i][j]=true; ans[s[j]-‘0‘]++; que[s[j]-‘0‘].push(make_pair(i,j)); cnt++; } } } while(cnt<n*m){ int xx=cnt; for(int i=1;i<=p;i++){ bfs(i); } if(cnt==xx)break;//剪枝 } for(int i=1;i<=p;i++){ cout<<ans[i]<<‘ ‘; } cout<<endl; return 0; }View Code