闲话
1974年第一次在东南亚打自由搏击就取得了冠军······
CF1974A
简单计数题
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
int t;
signed main(){
scanf("%lld",&t);
while(t--){
int x,y,ans=0,num=0;
scanf("%lld%lld",&x,&y);
ans+=y/2;
if(y&1) num+=4,ans++;
num+=ans*7;
if(x>num){
ans+=(int)ceil((double)(x-num)/15.0);
}
printf("%lld\n",ans);
}
}
CF1974B
洛谷题面翻译有误，建议自己看CF做题
照题面模拟即可，简单题
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int t,n;
int a[N],d[N];
char s[N];
int main(){
scanf("%d",&t);
while(t--){
scanf("%d",&n);
scanf("%s",s+1);
for(int i=1;i<=n;i++){
a[i]=s[i]-'a'+1;
}
sort(a+1,a+1+n);
int len=unique(a+1,a+1+n)-a-1;
for(int i=1;i<=len;i++){
int j=len-i+1;
d[a[i]]=a[j];
}
for(int i=1;i<=n;i++){
printf("%c",d[s[i]-'a'+1]+'a'-1);
}
printf("\n");
}
}
CF1974C
注意仔细审题，让你求的时美丽的三元组对数
非常巧妙的一道题，使我的大脑停止运转
首先我们考虑如果要成为一个美丽三元组对，就要满足在这个三元对上有两个对应位置上元素相同所以我们设两个三元组为 \(\{a,b,c\}\) 和 \(\{d,e,f\}\) 我们分别记录下 \(\{a,b\}==\{d,e\},\{a,c\}==\{d,f\},\{b,c\}==\{e,f\}\) 的个数设为 \(x,y,z\)
但是考虑到有可能有 \(\{a,b,c\}==\{d,e,f\}\) 的情况，所以我们在设一个 \(k\) 为这种情况的个数，因为这种情况会被前面连续统计三遍，所以最终答案即为 \(x+y+z-3*k\)
点击查看代码
#include<bits/stdc++.h>
#define pii pair<int,int>
#define int long long
using namespace std;
const int N=2e5+5;
int t,n;
int a[N];
map<pii,int>f,s,e;
map<pair<int,pii>,int>c;
signed main(){
scanf("%lld",&t);
while(t--){
scanf("%lld",&n);
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
}
f.clear();
s.clear();
e.clear();
c.clear();
int ans=0;
for(int i=3;i<=n;i++){
ans+=f[{a[i-2],a[i-1]}];
f[{a[i-2],a[i-1]}]++;
ans+=s[{a[i-1],a[i]}];
s[{a[i-1],a[i]}]++;
ans+=e[{a[i-2],a[i]}];
e[{a[i-2],a[i]}]++;
ans-=c[{a[i-2],{a[i-1],a[i]}}]*3;
c[{a[i-2],{a[i-1],a[i]}}]++;
}
printf("%lld\n",ans);
}
}
CF1974D
一道水题
sb题面翻译漏掉了一条重要信息导致我卡了好久
两个物体均要进行移动，不能只有一个物体动，例如样例中第4个SN的情况就不行。
珍爱生命，别看翻译
然后就手模一下就知道，我们把 NS，EW 捆绑在一起，分给同一个机器人，剩下的多的就平分给两个机器人，若剩下的是奇数无法平分就NO
还有要特判只有一个机器人动的情况，再把它捆绑的步数，就是一组NS或EW分给另一个机器人就可以了
代码实现有点复杂，我写了100行
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int t,n;
int a[N],pr[N],ph[N];
char s[N];
int main(){
scanf("%d",&t);
while(t--){
scanf("%d",&n);
scanf("%s",s+1);
int u=0,d=0,l=0,r=0;
for(int i=1;i<=n;i++){
if(s[i]=='N') a[i]=1,u++;
if(s[i]=='S') a[i]=2,d++;
if(s[i]=='E') a[i]=3,l++;
if(s[i]=='W') a[i]=4,r++;
}
if(l>=r){
int num=l-r;
if(num&1){
printf("NO\n");
continue;
}
pr[3]=num/2+r;
ph[3]=num/2;
pr[4]=r;
if(num==0&&r>1){
pr[3]--;pr[4]--;
ph[3]++;ph[4]++;
}
}
else{
int num=r-l;
if(num&1){
printf("NO\n");
continue;
}
pr[4]=num/2+l;
ph[4]=num/2;
pr[3]=l;
if(num==0&&l>1){
pr[4]--;pr[3]--;
ph[4]++;ph[3]++;
}
}
if(u>=d){
int num=u-d;
if(num&1){
printf("NO\n");
continue;
}
ph[1]=num/2+d;
pr[1]=num/2;
ph[2]=d;
if(num==0&&d>1){
ph[1]--;ph[2]--;
pr[1]++;pr[2]++;
}
}
else{
int num=d-u;
if(num&1){
printf("NO\n");
continue;
}
ph[2]=num/2+u;
pr[2]=num/2;
ph[1]=u;
if(num==0&&u>1){
ph[1]--;ph[2]--;
pr[1]++;pr[2]++;
}
}
if(!pr[1]&&!pr[2]&&!pr[3]&&!pr[4]){
printf("NO\n");
continue;
}
if(!ph[1]&&!ph[2]&&!ph[3]&&!ph[4]){
printf("NO\n");
continue;
}
for(int i=1;i<=n;i++){
if(pr[a[i]]){
printf("R");
pr[a[i]]--;
}
else{
printf("H");
ph[a[i]]--;
}
}
printf("\n");
}
}