A
题面:
对于给定的一个正整数 \(n\),判断 \(n\) 是否能分成若干个正整数之和(可以重复),其中每个正整数都能表示成两个质数乘积。
思路:
随随便便找规律就找出来了。
代码:
int q;
int main(){
q=read();
while(q--) {
ll n=read();
if(n<4) {
putchar('0'); putchar('\n');
continue ;
}
if(n%2==0) {
putchar('1'); putchar('\n');
continue ;
}
if(n==9) {
putchar('1'); putchar('\n');
continue ;
}
if(n<=11) {
putchar('0'); putchar('\n');
continue ;
}
putchar('1'); putchar('\n');
}
}
B
题面:
有一个长度为 \(n\) 的自然数序列 \(a\),要求将这个序列恰好分成至少 \(m\) 个连续子段。每个子段的价值为该子段的所有数的按位异或。要使所有子段的价值按位与
的结果最大,输出这个最大值。
思路:
贪心的,从高位到低位考虑,前期分的段越多越好。
对于每一位,如果这个 \(01\) 序列合法,那么前边掰掉合法的一段,后面剩下的一段还是合法的。
后面分段的时候要保证前面的高位还是合法的,段数只有可能少没有可能多。
那么前面应该尽可能多分几段有利于后面的合并。
int q, n, m;
int sz[2003][31];
int a, ans;
int sta[2003], top;
int A[2003], tt;
bool pd[35];
int main() {
q=read();
while(q--) {
n=read(); m=read(); ans=0;
memset(sz, 0, sizeof(sz));
memset(pd, 0, sizeof(pd));
for(int i=1; i<=n; ++i) {
cin>>a;
int js=0;
while(a) {
if(a&1) sz[i][js]=1;
++js;
a>>=1;
}
for(int j=0; j<=30; ++j) sz[i][j]+=sz[i-1][j];
}
int maxx=-1;
for(int i=30; i>=0; --i) {
if(sz[n][i]>=m) {maxx=i; break ;}
}
if(maxx==-1) {cout<<0<<'\n'; continue ;}
pd[maxx]=1; top=0;
for(int j=maxx; j>=0; --j) {
if((sz[n][j]&1)!=(sz[n][maxx]&1)) continue ;
int sum=0, js=0, tt=0;
for(int i=1; i<=n; ++i) {
if(sz[i][j]-sz[i-1][j]) sum++;
if(sum&1) {
bool flag=1;
for(int k=j; k<=maxx; ++k) {
if(pd[k]==0) continue ;
if(((sz[i][k]-sz[A[tt]][k])&1)==0) {
flag=0; break;
}
}
if(flag) {
sum=0;
A[++tt]=i;
}
}
}
if(tt>=m) {
top=tt;
for(int i=1; i<=top; ++i) sta[i]=A[i];
pd[j]=1;
ans+=(1<<j);
}
}
cout<<ans; putchar('\n');
}
}
标签:sz,10.31,子段,int,js,read,解题,--,集训
From: https://www.cnblogs.com/Konnyaku41377/p/16846098.html