T1
考场用时：\(30\) min
期望得分：\(100\) pts
实际得分：\(100\) pts
考虑最小的单元是 \(4=2\times 2\)，所以对于所有的数按照 \(\mod 4\) 的余数来分四类。
对于比较小的数，打表求出，大的一定有解，构造方案在注释里。
#include<bits/stdc++.h>
#define ll long long
#define int long long
//#define ull unsigned long long
#define lc(k) k<<1
#define rc(k) k<<1|1
#define lb lower_bound
#define orz cout<<"gzn ak ioi\n"
const int MAX=1e6+10;
const int MOD=1e9+7;
using namespace std;
inline char readchar() {
static char buf[100000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}
inline int read() {
#define readchar getchar
int res = 0, f = 0;
char ch = readchar();
for(; !isdigit(ch); ch = readchar()) if(ch == '-') f = 1;
for(; isdigit(ch);ch = readchar()) res = (res << 1) + (res << 3) + (ch ^ '0');
return f ? -res : res;
}
inline void write(int x) {
if(x<0){putchar('-');x=-x;}
if(x>9) write(x/10);
putchar(x%10+'0');
}
/*
对于<4的，无解
对于>=4的
n%4=0 n>=4时2*2+2*2...
n%4=1 >=9的：3*3+2*2+2*2...
n%4=2 >=6的：2*3+2*2+2*2
n%4=3 3*5+2*2+2*2...
先打出 15 以内的表，其他的按照上述构造方式，都有解。
*/
int biao[20]={0,0,0,0,1,0,1,0,1,1,1,0,1,1,1,1};
signed main(){
// freopen("a.in","r",stdin);
// freopen("a.out","w",stdout);
int T=read();
while(T--){
int n=read();
if(n<=15) write(biao[n]);
else putchar('1');
putchar('\n');
}
return 0;
}
T2
考场用时：\(80\) min
期望得分：\(20\) pts
实际得分：\(20\) pts
这题考场上想到了由高到低按位贪心，但是没想到怎么 check，其实用 dp 来求出不打乱前 \(i-1\) 位并且保证第 \(i\) 位是 \(1\) 的前提下，能够分的最大段数，与 \(m\) 比较，计入贡献即可。
#include<bits/stdc++.h>
#define ll long long
#define int long long
//#define ull unsigned long long
#define lc(k) k<<1
#define rc(k) k<<1|1
#define lb lower_bound
#define orz cout<<"gzn ak ioi\n"
const int MAX=1e6+10;
const int MOD=1e9+7;
using namespace std;
inline char readchar() {
static char buf[100000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}
inline int read() {
#define readchar getchar
int res = 0, f = 0;
char ch = readchar();
for(; !isdigit(ch); ch = readchar()) if(ch == '-') f = 1;
for(; isdigit(ch);ch = readchar()) res = (res << 1) + (res << 3) + (ch ^ '0');
return f ? -res : res;
}
inline void write(int x) {
if(x<0){putchar('-');x=-x;}
if(x>9) write(x/10);
putchar(x%10+'0');
}
int a[MAX],f[MAX],sum[MAX];
signed main(){
int T=read();
while(T--){
int n=read(),m=read(),ans=0;
for(int i=1;i<=n;i++) a[i]=read();
for(int i=1;i<=n;i++) sum[i]=sum[i-1]^a[i];
for(int i=29;i>=0;i--){
memset(f,-1,sizeof f);
f[0]=0;
for(int j=1;j<=n;j++)
for(int k=0;k<j;k++){
if(f[k]==-1) continue;
int t=sum[j]^sum[k];
if((ans&t)<ans) continue;//保证前i-1位不变
if(!(t&(1ll<<i))) continue;//保证该位为1
f[j]=max(f[k]+1,f[j]);
}
if(f[n]>=m) ans|=(1ll<<i);//能分成>=m段
}
cout<<ans<<endl;
}
return 0;
}
T3
考场用时：\(1.5\) h
期望得分：\(10\) pts
实际得分：\(10\) pts
这题是一个大分讨 dp，考场开始想写组合做法，但是推着推着发现细节巨多，巨麻烦，就弃了，写了个暴力本地挂着，一边跑一边对着跑出来的找规律，除了一个没什么用的 \(f_n=f_{n-1}+f_{n-2}\) 之外没找到什么规律，暴力一直跑到考试结束只跑出来 \(n=14\) 以内的，于是把 \(14\) 以内的表粘上就走人了。