A. Thorns and Coins
这题其实就是判断一下在第一个连续2个荆棘前面的所有硬币数。
#include <bits/stdc++.h>
using namespace std;
const int maxn=50;
int t,n;
char a[maxn+5];
int main(){
// freopen("1.txt","r",stdin);
scanf("%d",&t);
while (t--){
scanf("%d",&n);
scanf("%s",a);
int ans=0;
for (int i=0;i<n;i++){
if (a[i]=='*'&&a[i+1]=='*')
break;
if (a[i]=='@')
ans++;
}
printf("%d\n",ans);
}
return 0;
}
B. Chaya Calendar
一开始还想了一下结果会不会比2^63更大然后爆ll，交一下发现并不会，一个朴素的模拟。
#include <bits/stdc++.h>
using namespace std;
const int maxn=100;
int t,n;
long long a[maxn+5];
int main(){
// freopen("1.txt","r",stdin);
scanf("%d",&t);
while (t--){
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%lld",&a[i]);
long long ans=0,last=0;
for (int i=1;i<=n;i++){
ans=(a[i]*((int)(last/a[i])+1));
last=ans;
}
printf("%lld\n",ans);
}
return 0;
}
C. LR-remainders
正着做要求乘积动态删点有点麻烦，但是因为这个比较简单，只有删除操作，所以直接离线做，倒着处理，就变成不断加点维护乘积就行了。
#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5;
int t,n,m;
int a[maxn+5];
char s[maxn+5];
int ans[maxn+5];
int main(){
// freopen("1.txt","r",stdin);
scanf("%d",&t);
while (t--){
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)
scanf("%d",&a[i]);
scanf("%s",s+1);
int l=1,r=n;
for (int i=2;i<=n;i++){
if (s[i-1]=='L')
l++;
else
r--;
}
ans[n]=a[l]%m;
int i;
for (i=n-1;i;i--){
if (s[i]=='L')
ans[i]=(ans[i+1]*a[l-1])%m,l--;
else
ans[i]=(ans[i+1]*a[r+1])%m,r++;
}
for (int i=1;i<=n;i++)
printf("%d ",ans[i]);
putchar('\n');
}
return 0;
}
D. Card Game
对于除了王牌外任意一种花色的牌，如果它们是偶数个，直接从小到大两两消掉就可以，如果是奇数个，就和随便一张王牌消掉。如果王牌不够了，这个就是impossible的情况，然后最后同理消掉剩下的王牌。
#include <bits/stdc++.h>
using namespace std;
const int maxn=100;
int t,n;
char king;
char c[5]={0,'C','D','H','S'};
vector<int> card['Z'];
char str[maxn+5];
int main(){
// freopen("1.txt","r",stdin);
scanf("%d",&t);
while (t--){
scanf("%d",&n);
scanf("%s",str);
king=str[0];
int lim=n<<1;
card['C'].clear(),card['D'].clear(),card['H'].clear(),card['S'].clear();
for (int i=1;i<=lim;i++){
scanf("%s",str);
card[str[1]].push_back(str[0]-'0');
}
int res=0;
for (int i=1;i<=4;i++)
if (c[i]!=king)
res+=card[c[i]].size()%2;
if (res>card[king].size())
puts("IMPOSSIBLE");
else{
int pos=0;
sort(card[king].begin(),card[king].end());
for (int i=1;i<=4;i++)
if (c[i]!=king){
sort(card[c[i]].begin(),card[c[i]].end());
for (int j=1;j<card[c[i]].size();j+=2)
printf("%d%c %d%c\n",card[c[i]][j-1],c[i],card[c[i]][j],c[i]);
if (card[c[i]].size()%2)
printf("%d%c %d%c\n",card[c[i]][card[c[i]].size()-1],c[i],card[king][pos++],king);
}
for (int i=pos+1;i<card[king].size();i+=2)
printf("%d%c %d%c\n",card[king][i-1],king,card[king][i],king);
}
}
return 0;
}
E. Final Countdown
对于任意的一个时间，如果只考虑个位，就是正常倒计时；再考虑其他位，例如十位，会多花多长时间？很显然就是前面的数，比如12345，它的十位4就要多花1234秒，百位就要多花123秒，相当于每个数位都单独倒计时了。所以12345的答案是12345+1234+123+12+1.
接着一开始直接想歪到高精度了，没存高精度板子还花半个小时打了下（太蠢了），显然会TLE。但是其实不需要高精度，直接模仿加法进位就行了，有点像但不完全是。
#include <bits/stdc++.h>
using namespace std;
const int maxn=4e5;
int t,n;
char str[maxn+5];
int d[maxn+5];
int sum[maxn+5];
int ans[(maxn<<1)+5];
int main(){
// freopen("1.txt","r",stdin);
scanf("%d",&t);
while (t--){
scanf("%d",&n);
scanf("%s",str+1);
for (int i=n;i;i--)
d[n-i+1]=str[i]-'0';
for (int i=1;i<=n;i++)
sum[i]=d[i]+sum[i-1];
int pos=0;
int res=0;
for (int i=1;i<=n;i++){
ans[++pos]=sum[n]-sum[i-1]+res;
res=ans[pos]/10,ans[pos]%=10;
}
int vis=0;
if (res){
printf("%d",res);
vis=1;
}
for (int i=pos;i;i--)
if (vis||ans[i]){
printf("%d",ans[i]);
vis=1;
}
putchar('\n');
}
return 0;
}
F. Feed Cats
有点像时间调度问题，那就可以转换成时间调度问题。对于每个时间点，我们视为一个可以接受也可以不接受的任务，这个任务的价值是这个时间点被多少个线段包括了，这个任务的开始时间是这些包括该点的线段的最早起点，结束时间是这些包括该点的线段的最晚终点。直接转换成时间调度问题，选择几个任务使得价值最大化，同一时间只能执行一个任务。
预处理出任务的价值、开始时间、结束时间。任务的价值预处理是一个区间累加，可以用差分。开始和结束时间的维护，我一开始想用线段树维护，结果结束了也没有写完，TAT。打完后发现也可以用差分的思想，因为我们只要求快速的区间修改，而不那么在乎查询速率。那就可以对每个区间的起点打上一个Node，记录修改的最值和延续的终点，然后用类似单调队列做。