2019.10.16考试解题报告
总结
期望得分：(100 + 0 + 10)
实际得分：(100 + 0 + 10)
好久没有(T3)有分过了……(T1)找规律题，打打表就行了，(T2)位运算题，我不会，(T3)打表得了(10)分
思路
T1
首先可以直接打(100)之前的表，然后就会发现除了(1、2、3、5、7、11)以外，所有的数都可以被凑出来，然后就可以特判了……我懒，直接把打表的代码交了上去，下面是打表结果
T2
题意：
(q)组数据。
给你一个长为(n)的非负数序列(a)。
定义一个区间的权值为区间的异或和。
定义一个划分的权值为分出的区间的权值的按位与的值。
要求至少把序列分成(m)个非空字段,求满足条件的划分的最大权值。
(from solution)
因为异或运算具有交换律且(x xor x = 0),所以区间异或和可以由两个前缀异或和异或得到。
考虑从高位到低位确定答案的二进制位,然后考虑判断是否能分成至少(m)段。
如何判断是否能分成至少(m)段?
"能分成至少(m)段"与"最多能分成的段数(>=m)"等价。
令(dp[i] =) "(a[1..i])这一段数最多能分成多少段"
转移就是直接枚举上一段的末尾(j),如果([j+1,i])可以组成一段,那么就把(dp[i] = max(dp[i],dp[j] + 1);)
这样(DP)的复杂度是(O(n^2))。
总复杂度就是(O(q * log()值域() * DP) = O(30qn^2) ≈ 3.6 * 10^8),因为常数较小可以过。
T3
只会打表，看程序吧……
代码
T1
考场满分代码
/*
By:Loceaner
*/
#include <cstdio>
#include <cstring>
#include <iostream>
#define int long long
using namespace std;
inline int read() {
char c = getchar();
int x = 0, f = 1;
for( ; !isdigit(c); c = getchar()) if(c == '-') f = -1;
for( ; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + (c ^ 48);
return x * f;
}
const int N = 5e3 + 11;
int q, n;
int vis[N], p[N], cnt, f[N];
void prepare() {
vis[0] = vis[1] = 1;
for(int i = 2; i <= 1000; i++) {
if(!vis[i]) p[++cnt] = i;
for(int j = 1; j <= cnt; j++) {
if(i * p[j] > 1000) break;
vis[i * p[j]] = 1;
if(i % p[j] == 0) break;
}
}
bool flag = 0;
for(int i = 1; i <= cnt; i++) {
for(int j = 1; j <= cnt; j++) {
if(p[i] * p[j] > 1000) break;
f[p[i] * p[j]] = 1;
}
}
for(int i = 1; i <= 1000; i++) {
if(f[i]) continue;
for(int j = 2; j < i; j++)
if(f[j] && f[i - j]) {
f[i] = 1;
break;
}
}
}
signed main() {
freopen("a.in", "r", stdin);
freopen("a.out", "w", stdout);
prepare();
q = read();
while(q--) {
n = read();
if(n <= 50) cout << f[n] << '
';
else cout << "1
";
}
return 0;
}
T2
正解
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int q,n,m,ans,x,s[1005],f[1005];
int rd(){
int re=0,f=1;char c=getchar();
while ((c<'0')||(c>'9')) {if (c=='-') f=-f;c=getchar();}
while ((c>='0')&&(c<='9')) {re=re*10+c-'0';c=getchar();}
return re*f;
}
int Max(int x,int y){
return ((x>y)?x:y);
}
int main(){
freopen("b.in","r",stdin);
freopen("b.out","w",stdout);
q=rd();
for (;q>0;--q){
n=rd();m=rd();
s[0]=0;
for (int i=1;i<=n;++i){
x=rd();s[i]=s[i-1]^x;
}
ans=0;
for (int i=29;i>=0;--i){
memset(f,0,sizeof(f));
f[0]=1;
for (int j=1;j<=n;++j){
for (int k=0;k<j;++k) if (f[k]>0){
x=s[j]^s[k];
if (((ans&x)>=ans)&&((x&(1<<i))>0))
f[j]=Max(f[k]+1,f[j]);
}
}
if (f[n]>m) ans|=(1<<i);
}
cout<<ans<<'
';
}
return 0;
}
T3
(10)分打表
//知识点:
/*
By:Loceaner
*/
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
inline int read() {
char c = getchar();
int x = 0, f = 1;
for( ; !isdigit(c); c = getchar()) if(c == '-') f = -1;
for( ; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + (c ^ 48);
return x * f;
}
const int N = 1100;
int a[N][N];
int T, p, n, m;
int main() {
freopen("c.in", "r", stdin);
freopen("c.out", "w", stdout);
a[0][0] = 1;
a[1][0] = 0,a[1][1] = 1;
a[2][0] = 0,a[2][1] = 0,a[2][2] = 2;
a[3][0] = 0,a[3][1] = 1,a[3][2] = 2,a[3][3] = 3;
a[4][0] = 1,a[4][1] = 2,a[4][2] = 10,a[4][3] = 6,a[4][4] = 5;
a[5][0] = 4,a[5][1] = 20,a[5][2] = 28,a[5][3] = 44,a[5][4] = 16,a[5][5] = 8;
a[6][0] = 29,a[6][1] = 104,a[6][2] = 207,a[6][3] = 180,a[6][4] = 151,a[6][5] = 36,a[6][6] = 13;
a[7][0] = 206,a[7][1] = 775,a[7][2] = 1288,a[7][3] = 1407,a[7][4] = 830,a[7][5] = 437,a[7][6] = 76,a[7][7] = 21;
a[8][0] = 1708,a[8][1] = 6140,a[8][2] = 10366,a[8][3] = 10384,a[8][4] = 7298,a[8][5] = 3100,a[8][6] = 1138,a[8][7] = 152,a[8][8] = 34;
a[9][0] = 15702,a[9][1] = 55427,a[9][2] = 91296,a[9][3] = 92896,a[9][4] = 63140, a[9][5] = 31278,a[9][6] = 10048,a[9][7] = 2744,a[9][8] = 294,a[9][9] = 55;
a[10][0] = 159737,a[10][1] = 553802,a[10][2] = 903037,a[10][3] = 911512,a[10][4] = 633946,a[10][5] = 314044,a[10][6] = 116458,a[10][7] = 29368,a[10][8] = 6253,a[10][9] = 554,a[10][10] = 89;
a[11][0] = 1780696,a[11][1] = 6087992,a[11][2] = 9832848,a[11][3] = 9913152,a[11][4] = 6931680,a[11][5] = 3543360,a[11][6] = 1343664,a[11][7] = 389232,a[11][8]= 79368,a[11][9] = 13640,a[11][10] = 1024,a[11][11] = 144;
a[12][0] = 21599745,a[12][1] = 72994152,a[12][2] = 117032570,a[12][3] = 117788056,a[12][4] = 82956135,a[12][5] = 43096224,a[12][6] = 16993884,a[12][7] = 5113632,a[12][8] = 1194639,a[12][9] = 201720,a[12][10] = 28746,a[12][11] = 1864,a[12][12] = 233;
T = read(), p = read();
while(T--) {
n = read(), m = read();
cout << a[n][m] % p << '
';
}
return 0;
}
(std)
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=2005;
int q,n,m,u,v;
LL p,ans,f[N][N][5],x;
int rd(){
int re=0,f=1;char c=getchar();
while ((c<'0')||(c>'9')) {if (c=='-') f=-f;c=getchar();}
while ((c>='0')&&(c<='9')) {re=re*10+c-'0';c=getchar();}
return re*f;
}
int main(){
freopen("c.in","r",stdin);
freopen("c.out","w",stdout);
cin>>q>>p;
memset(f,0,sizeof(f));
f[1][1][0]=1ll;
f[2][2][0]=1ll;f[2][2][1]=1ll;
n=2000;
for (int i=2;i<n;++i)
for (int j=0;j<=n;++j){
for (int k=0;k<=4;++k){
x=f[i+1][j+1][0]+f[i][j][k];
x=(x<p)?x:(x-p);
f[i+1][j+1][0]=x;
u=j+((k%2)==0);
v=1+(k!=0);
x=f[i+1][u][v]+f[i][j][k];
x=(x<p)?x:(x-p);
f[i+1][u][v]=x;
}
if (f[i][j][0]>0ll){
f[i+1][j-1][4]=(f[i+1][j-1][4]+f[i][j][0]*(LL)(j-1))%p;
f[i+1][j][4]=(f[i+1][j][4]+f[i][j][0]*(LL)(i-j))%p;
}
if (f[i][j][1]>0ll){
x=f[i+1][j][3]+f[i][j][1];
x=(x<p)?x:(x-p);
f[i+1][j][3]=x;
f[i+1][j-1][4]=(f[i+1][j-1][4]+f[i][j][1]*(LL)(j-2))%p;
f[i+1][j][4]=(f[i+1][j][4]+f[i][j][1]*(LL)(i-j))%p;
}
if (f[i][j][2]>0ll){
x=f[i+1][j][3]+f[i][j][2];
x=(x<p)?x:(x-p);
f[i+1][j][3]=x;
f[i+1][j-1][4]=(f[i+1][j-1][4]+f[i][j][2]*(LL)(j-1))%p;
f[i+1][j][4]=(f[i+1][j][4]+f[i][j][2]*(LL)(i-j-1))%p;
}
if (f[i][j][3]>0ll){
x=f[i+1][j+1][3]+f[i][j][3];
x=(x<p)?x:(x-p);
f[i+1][j+1][3]=x;
f[i+1][j-1][4]=(f[i+1][j-1][4]+f[i][j][3]*(LL)(j-1))%p;
f[i+1][j][4]=(f[i+1][j][4]+f[i][j][3]*(LL)(i-j-1))%p;
}
if (f[i][j][4]>0ll){
x=f[i+1][j+1][3]+f[i][j][4];
x=(x<p)?x:(x-p);
f[i+1][j+1][3]=x;
if (j>0) f[i+1][j-1][4]=(f[i+1][j-1][4]+f[i][j][4]*(LL)(j))%p;
f[i+1][j][4]=(f[i+1][j][4]+f[i][j][4]*(LL)(i-j-2))%p;
}
}
for (;q>0;--q){
cin>>n>>m;
ans=(f[n][m][0]+f[n][m][1]+f[n][m][2]+f[n][m][3]+f[n][m][4])%p;
cout<<ans<<'
';
}
return 0;
}