C - Spiral Rotation
难得给C一次排面……好像也不算难得，无所谓了
题干的描述很抽象，但这题只要理解了题意就会很好写，这题的意思其实是：
首先将整个数组顺时针90度旋转一圈，然后除了最外圈再旋转，然后除了最外两圈再旋转……直至旋转完最内圈。
如果暴力模拟全部操作无疑会超时。我们注意到，全部操作结束后，最外圈一共旋转了90度，从外向内第二圈旋转了180度，第三圈旋转了270度……因而，我们可以很轻易的得出每一圈的最终旋转角度，然后对其取模即可每圈只用一次操作解决问题。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
void solve() {
int n;
cin>>n;
string s[n+2],ss[n+2];
for(int i=1;i<=n;i++){
cin>>s[i];
s[i]='x'+s[i];
ss[i]=s[i];
//cout<<s[i]<<endl;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
int cir=min(min(i,abs(i-n-1)),min(j,abs(j-n-1)));
//cout<<cir;
if(cir%4==0){
ss[i][j]=s[i][j];
}
if(cir%4==1){
ss[j][n+1-i]=s[i][j];
}
if(cir%4==2){
ss[n+1-i][n+1-j]=s[i][j];
}
if(cir%4==3){
ss[n+1-j][i]=s[i][j];
}
}
//cout<<endl;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cout<<ss[i][j];
}
cout<<endl;
}
}
D - ABA
我们考虑这样一种方法计算字符串中每一位的贡献：该位的贡献为该位与左侧所有同字符位之间间隔字符的数量和。
基于此，我们只需要对每一种字符存储三个变量：出现过的该字符数量和num，出现过的该字符下标和al，出现过的该字符的贡献总和sum。从左到右进行一次遍历，每到达一位，便通过$sum_i=num*(i-1)-al$这一公式计算该位的贡献并加到sum中，随后更新num和al，最后加和所有字符的sum便是最终答案。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
struct abc{
ll sum=0,num=0,al=0;
};
void solve() {
string s;
cin>>s;
map<char,abc> mp;
for(int i=0;i<s.size();i++){
if(mp.find(s[i])==mp.end()){
mp[s[i]].al=i;
mp[s[i]].num=1;
}
else{
mp[s[i]].sum+=mp[s[i]].num*(i-1)-mp[s[i]].al;
mp[s[i]].al+=i;
mp[s[i]].num++;
}
}
ll ans=0;
for(auto x:mp){
ans+=x.second.sum;
}
cout<<ans<<endl;
}
E - 3 Team Division
考虑到所有B的总和不超过1500，我们自然的想到可以利用DP来解题。
最基础的DP思路是$DP[N][A][B][C]$，四个状态分别为当前待安排人员与ABC三组的总战力，但我们易注意到这样会导致超时。考虑到符合要求的$A+B+C$的值是固定的且最终合规状态下ABC相等，我们可以省略掉对C的状态的枚举，从而将时间复杂度降低到可以接受的范围。状态转移方程的右式我们用以保存队员转移次数，注意因为我们省略了C的维度，所以在状态转移时要额外考虑队员转移到C队所带来的转移次数影响。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
void solve() {
int n;
cin>>n;
int dp[600][600];
memset(dp,0x3f,sizeof(dp));
dp[0][0]=0;
pair<int,int>peo[200];
int sum=0;
for(int i=0;i<n;i++){
cin>>peo[i].first>>peo[i].second;
sum+=peo[i].second;
}
//cout<<sum;
for(int i=0;i<n;i++){
for(int x=sum/3;x>=0;x--){
for(int y=sum/3;y>=0;y--){
dp[x][y]+=(peo[i].first!=3);
if(x-peo[i].second>=0){
dp[x][y]=min(dp[x][y],dp[x-peo[i].second][y]+(peo[i].first!=1));
}
if(y-peo[i].second>=0){
dp[x][y]=min(dp[x][y],dp[x][y-peo[i].second]+(peo[i].first!=2));
}
}
}
}
if(dp[sum/3][sum/3]>200||sum%3!=0)cout<<"-1";
else cout<<dp[sum/3][sum/3];
}
啥也不是，散会（讲师音）
哦对讲师现在吃住条件比我好，这下难绷了
