CSP-J 2026游记
CSP-J 2026游记
来晚了,主要是半期考没空写
本人蒟蒻一只,业余学OI,今年第一次考,没想到数学功底派上用场了。
T1
一眼模拟好吧,代码倒不是很好看,还想用substr,结果发现根本不会用,调了半天,还忘了string的第三个位置直接用[2]就好了。
::::success[code]
#include<bits/stdc++.h>
using namespace std;
bool check1(char s,char t)
{
if((s=='A'||s=='B'||s=='C')&&(t=='A'||t=='B'||t=='C'))
{
return 1;
}
if((s=='D'||s=='F')&&(t=='D'||t=='F'))
{
return 1;
}
return 0;
}
bool check2(char s,char t)
{
if(s=='A'&&t=='B'||s=='B'&&t=='C'||s=='D'&&t=='F')
{
return 1;
}
if(t=='A'&&s=='B'||t=='B'&&s=='C'||t=='D'&&s=='F')
{
return 1;
}
return 0;
}
int main()
{
freopen("travel.in","r",stdin);
freopen("travel.out","w",stdout);
string c1,s1,c2,s2;
cin>>c1>>s1>>c2>>s2;
if(c1==c2)
{
cout<<"1";
}
else
{
cout<<"0";
}
if(c1==c2&&s1.substr(0,2)==s2.substr(0,2))
{
cout<<"1";
}
else
{
cout<<"0";
}
if(c1==c2&&s1.substr(0,2)==s2.substr(0,2)&&check1(s1[2],s2[2]))
{
cout<<"1";
}
else
{
cout<<"0";
}
if(c1==c2&&s1.substr(0,2)==s2.substr(0,2)&&check1(s1[2],s2[2])&&check2(s1[2],s2[2]))
{
cout<<"1";
}
else
{
cout<<"0";
}
return 0;
}
::::
T2
本来觉得应该很简单,结果推了一个小时。
本来要模拟的,不过想了想复杂度还是算了。
我一个同学就是模拟的,考场上喜提6GB内存,最后48分。
突然想起来了双指针,而且还会用,写代码30min,调20min,发现一直不对,然后发现
if(x[i]>=x[j])
{
x[i]-=minn;
j--;
}
if(x[i]<=x[j])
{
x[j]-=minn;
i++;
}
我觉得这样写比较优雅,结果我前面一次把后一次要比较的给改了?
最后也是顺利调好过了大样例.
::::success[code]
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,x[200001],c[200001],pre,ans;
signed main()
{
freopen("string.in","r",stdin);
freopen("string.out","w",stdout);
cin>>n;
for(int i=1;i<=n;i++)
{
scanf("%lld %c",&x[i],&c[i]);
pre+=x[i];
}
for(int i=1,j=n;i<=j;)
{
int p=x[i],q=x[j],a=i,b=j;
int minn=min(p,q);
if(c[i]!=c[j])
{
ans+=minn;
}
if(p>=q)
{
x[a]-=minn;
j--;
}
if(p<=q)
{
x[b]-=minn;
i++;
}
}
cout<<ans;
return 0;
}
::::
T3
一眼数学?还想着背包DP,发现根本不转移好吧。
不过我也不会DP
然后就开始想贪心,把草稿纸快用完的时候想起来&的特性.
先分解二进制,并统计次数,把第一次足够m个的位数记录下来,break,然后全体取模,sort一遍取前m个就好了。
我也没有证明贪心策略,但是大样例全过了,不知道为什么95。
::::success[code]
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,cnt[31],use[200000],fm=31,ans=2147483647;
struct number
{
int l,x[31];
};
number q[200000];
bool cmp(number a,number b)
{
return a.l>b.l;
}
void push(int i)
{
int t=q[i].l,z=30;
string s="";
while(t)
{
q[i].x[z]=(t&1);
if(t&1)
{
cnt[z]++;
}
t>>=1;
z--;
}
return;
}
signed main()
{
freopen("and.in","r",stdin);
freopen("and.out","w",stdout);
cin>>n>>m;
for(int i=0;i<n;i++)
{
scanf("%lld",&q[i].l);
push(i);
}
for(int i=0;i<=30;i++)
{
if(cnt[i]>=m)
{
fm=i;
break;
}
}
if(fm==31)
{
cout<<"0";
}
else
{
long long lim=1<<(31-fm);
for(int i=0;i<n;i++)
{
q[i].l%=lim;
}
sort(q,q+n,cmp);
for(int i=0;i<m;i++)
{
ans=ans&q[i].l;
}
cout<<ans;
}
return 0;
}
::::
T4
完全不会,没时间骗分
不知道写了啥
::::success[code]
#include<bits/stdc++.h>
using namespace std;
int n,m,a[500001],desk[500001],u[500001],w[500001],s;
int main()
{
freopen("card.in","r",stdin);
freopen("card.out","w",stdout);
cin>>n>>m;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
for(int i=1;i<=n;i++)
{
for(int j=i;j<=n;j++)
{
if(u[j])
{
continue;
}
for(int k=1;k<=s;k++)
{
if(desk[k]==a[j])
{
for(int l=k;l<=s;l++)
{
desk[l]=0;
u[l]=0;
}
s=k-1;
break;
}
}
desk[++s]=a[j];
u[j]=1;
}
}
for(int i=1;i<=s;i++)
{
printf("%d ",desk[s]);
}
return 0;
}
::::