本次题目绝大多数为原创题，没有出太大的锅。题目并不很难， 小时的赛时内已有人 AK。
A.魔法师的难题
枚举所有可能用得到的美丽数，看这个美丽数是否小于等于 .
通过枚举所有小于等于 的数字，再判断它是否为美丽数，需要枚举并判断至多
次，如果使用特殊的优化，现行的微机无法在
s 内算出.
C++ 代码：
#include<cstdio>
int main()
{
int n;scanf("%d",&n);
int base=0,answer=0;
for(int i=1;i<=9;i++)
{
base=base*10+1;//base={1,11,111,1111,...}
for(int j=1;j<=9;j++)
if(base*j<=n)//base*j={1,2,...,9,11,22,...,99,111,...}
answer++;
}
printf("%d",answer);
return 0;
}
Python 代码：
n=int(input())
answer=0
for i in range(1,10):
for j in range(1,10):
if int('1'*i)*j<=n:#'1'*i == '11...1'(i个1的字符串)
answer+=1
print(answer)
B.列项构造
为正整数的充要条件为
且
，记
是一个正整数，则充要条件为
引理
均为整数，
和
可以推出
.
[证明]：存在整数 使得
成立，存在整数
使得
，则存在整数
使得
，得出
.
由 ，进而得出
即
.
每个 对应一个唯一的
，也对应一个唯一的正整数解
，故所求为
的约数个数.
对 质因数分解为
我们考虑取一个数
让他整除
，那么
的质因数都能在
那里找到，而且它的每个质因数
的重数
都小于等于
的重数
，即有
，共
种。如果有一个质因数的重数不同，那么这两个数不同，根据乘法原理，我们可以求出
的约数个数为
如果
那么
因而对 ，
分别作因式分解即可，否则复杂度就会爆炸♪.
对于 的要求：因为
时，方程恒成立，故每一对
的解集都包含一个
的解，刨除这一个解即可.
注： 这似乎没有看起来那么简单？反正名字已经不太对劲了，它原来真的是个构造题。
C++ 代码：
#include<cstdio>
#include<map>
using namespace std;
map<int,int> m;
//m 是质数集到质数对应指数集的映射
void divide_into_factors(int n)//质因数分解
{
//注：本函数 n 不能为 0，否则会死循环，时间复杂度 O(√n)
for(int i=2;i*i<=n;i++)
while(n%i==0)m[i]++,n/=i;
if(n!=1)m[n]++;
}
int main()
{
int t;scanf("%d",&t);
while(t--)
{
m.clear();
int n,k;scanf("%d%d",&n,&k);
//kn² 质因数分解，不会有人傻到要乘一块再分解吧！
divide_into_factors(k);
divide_into_factors(n);
divide_into_factors(n);
//遍历 m，获得每个质数对应的指数，进而求得约数个数
int ans=1;//对于一个 1e18 范围内的数，约数个数最多有 1e5 个
for(auto[p,b]:m)ans*=b+1;
printf("%d\n",ans-1);//除去 x=y 的解
}
return 0;
}
Python 代码：
t=int(input())
def divide_into_factors(n):#质因数分解
#注：本函数 n 不能为 0，否则会死循环，时间复杂度 O(√n)
i=2
while i*i<=n:
if n%i==0:
if i not in m: m[i]=0
while n%i==0: m[i]+=1;n//=i
i+=1
if n!=1:
if n not in m: m[n]=0
m[n]+=1
while t:
t-=1
m=dict()#创造一个字典作质数到指数的映射用
n,k=map(int,input().split())
# kn² 质因数分解，不会有人傻到要乘一块再分解吧！
divide_into_factors(n)
divide_into_factors(n)
divide_into_factors(k)
ans=1
for b in m.values(): ans*=b+1
print(ans-1)#除去 x=y 的解
什么？你说我欺负 C 语言没有 STL 容器？
C 代码：
#include<stdio.h>
#include<stdlib.h>
int s[100],top;//s 下标 [0,top) 记录按照重数记录质因数
//10^6 范围内数的质因数重数和最多为 19，约为 log_2(10^6)
void divide_into_factors(int n)//质因数分解
{
//注：本函数 n 不能为 0，否则会死循环，时间复杂度 O(√n)
int i=2;for(;i*i<=n;i++)
while(n%i==0)s[top++]=i,n/=i;
if(n!=1)s[top++]=n;
}
int cmp(const void*a,const void*b)//qsort 的 cmp 函数，不懂百度
{
return (*(int*)a-*(int*)b);
}
int main()
{
int t;scanf("%d",&t);
while(t--)
{
top=0;
int n,k;scanf("%d%d",&n,&k);
//kn² 质因数分解，不会有人傻到要乘一块再分解吧！
divide_into_factors(k);
divide_into_factors(n);
divide_into_factors(n);
//遍历 m，获得每个质数对应的指数，进而求得约数个数
int ans=1,b=1;
//对于一个 1e18 范围内的数，约数个数最多有 1e5 个
// b=1 表示第一个质因数有一重
qsort(s,top,sizeof(int),cmp);//排序
s[top]=-1;//s[top]作特殊处理，不等于前一个数
int i=1;for(;i<=top;i++)
if(s[i]==s[i-1])b++;//相等重数增加
else ans*=b+1,b=1;//不相等表示之前数重数处理完毕，下一个数重数记上 1
printf("%d\n",ans-1);//除去 x=y 的解
}
return 0;
}
C.致胜锦囊
签到题，输出 "RUSHB" 即可通过.
因为 PHP 是世界上最好的程序设计语言，所以通过 PHP 我们得到了本题最短解。
PHP 代码：
RUSHB
D.路线规划
简单的搜索题，数据范围小到不剪枝都能让 Python 递归通过。特意没有出成最短路问题。
C++ 代码：
#include<cstdio>
#include<cmath>
double ans=1e100;//预设一个很大的值
int vis[10],x[10],y[10],w[10],n,w0;
void dfs(double nowt,int step,int W,int lastx,int lasty)
{
//此处可以剪枝 if(nowdis>ans)return; 后面的比较也可以去掉
if(step==n)//每个资源点都走过了，比较一下答案的大小
{
if(nowt<ans)ans=nowt;return;//找到了更近的路
}
for(int i=0;i<n;i++)if(!vis[i])
{
vis[i]=1;//标记，否则程序死循环了
//递归 时间加上走的这段，步数加一，总重量增加w_i，坐标更新为(x_i,y_i)
dfs(nowt+ W *hypot(x[i]-lastx,y[i]-lasty),step+1, W +w[i],x[i],y[i]);
//hypot(x,y)表示 √(x²+y²)，用来计算距离
//写成sqrt(x*x,y*y)的形式也没问题
vis[i]=0;//回溯，去掉之前的痕迹
}
}
int main()
{
scanf("%d%d",&n,&w0);
for(int i=0;i<n;i++)scanf("%d",x+i);
for(int i=0;i<n;i++)scanf("%d",y+i);
for(int i=0;i<n;i++)scanf("%d",w+i);
dfs(0,0,w0,0,0);//初始时间 0，步数 0，重量 w0，在原点 (0,0)
printf("%.6lf",ans);
return 0;
}
Python 代码：
n,w0=map(int,input().split())
x=list(map(int,input().split()))
y=list(map(int,input().split()))
w=list(map(int,input().split()))
ans=1e100#预设一个很大的值
vis=[0 for i in range(n)]
import math
def dfs(nowt,step,W,lastx,lasty):
global ans
#此处可以剪枝 if nowdis>ans:return 后面的比较也可以去掉
if step==n:#每个资源点都走过了，比较一下答案的大小
ans=min(ans,nowt);return
for i in range(n):
if vis[i]==0:
vis[i]=1#标记，否则程序死循环了
#递归 时间加上走的这段，步数加一，总重量增加w_i，坐标更新为(x_i,y_i)
dfs(nowt+ W *math.hypot(x[i]-lastx,y[i]-lasty),step+1, W +w[i],x[i],y[i])
#math.hypot(x,y)表示 √(x²+y²)，用来计算距离
#写成math.sqrt(x*x,y*y)的形式也没问题
vis[i]=0#回溯，去掉之前的痕迹
dfs(0,0,w0,0,0)#初始时间 0，步数 0，重量 w0，在原点 (0,0)
print(ans)
E.简单的常系数线性齐次递推问题
简单的递推问题，递推式写得清清楚楚.
本题坑点：
- 可能
，
- 输入有负整数，结果要求余数是正整数。
注：
什么是取模？取模有哪些性质？OI wiki 带余数除法、OI wiki 同余。
带余除法 设
，则必然存在 唯一 的一对整数
和
，使得
，满足
。
C++ 的代码
a%b的结果正负符号 往往 和a是一样的；在 Python 环境下，
a%b的结果正负符号和b是一样的；上面
a%b均表示除
的余数
。
在 Python 里，对正模数取模就不需要担心结果为负的情况了。
如果因为 Python 兼并大整数类，而且数据范围很小，你使用 Python 的话可以在最后取模.
很遗憾的是，本次数据较弱，没有卡掉某些没在最后面取正整数余数的程序。
C++ 代码1：
#include<cstdio>
#define mod 998244353
int c[51],a[1001];//a[i] 在全局区，初始值均为 0，方便后面的累加
int main()
{
int k,m;scanf("%d%d",&k,&m);
for(int i=1;i<=k;i++)scanf("%d",c+i);
for(int i=1;i<=k;i++)scanf("%d",a+i);
//递推过程中防止结果超出 long long 范围，每次都保存这个数%mod的结果，
//但是务必注意这个数可能是负数，都在-mod 到 mod 之间。
for(int n=k+1;n<=m;n++)
for(int i=1;i<=k;i++)
a[n]=(a[n]+1ll*c[i]*a[n-i])%mod;
//1ll 是 long long 型常数，隐式转换让 int 转成范围更广的 long long 型，否则乘法会溢出。
printf("%d",(a[m]+mod)%mod);
//直接写 a[m]，不对负数处理能在赛时通过本题的原因是，正好 a[m] 是个正数
return 0;
}
C++ 代码2：
#include<cstdio>
#define mod 998244353
int c[51],a[1001];//a[i] 在全局区，初始值均为 0，方便后面的累加
int main()
{
int k,m;scanf("%d%d",&k,&m);
for(int i=1;i<=k;i++)
{
scanf("%d",c+i);
if(c[i]<0)c[i]+=mod;//先处理成正数，最后结果依然是对的
}
for(int i=1;i<=k;i++)
{
scanf("%d",a+i);
if(a[i]<0)a[i]+=mod;//先处理成正数，最后结果依然是对的
}
for(int n=k+1;n<=m;n++)
for(int i=1;i<=k;i++)
a[n]=(a[n]+1ll*c[i]*a[n-i])%mod;
printf("%d",a[m]);
return 0;
}
Python3 代码1：
k,m = map(int,input().split())
c=[0]+list(map(int,input().split()))#[0] 占用 0 号下标
a=[0]+list(map(int,input().split()))#[0] 占用 0 号下标
if k< m:a+=[0 for i in range(m - k)]#补充列表/数组至下标 m
mod=998244353
for n in range(k+1,m+1):
for i in range(1,k+1):
a[n]+=c[i]*a[n - i]
print(a[m]%mod)
Python3 代码2：
k,m = map(int,input().split())
c=[0]+list(map(int,input().split()))#[0] 占用 0 号下标
a=[0]+list(map(int,input().split()))#[0] 占用 0 号下标
mod=998244353
while len(a) <= m:
a.append(sum([c[i]*a[-i]for i in range(1,k+1)]))
print(a[m]%mod)
F.正负串
注：这是本次比赛里唯一一道典题，甚至 GPT 都能做对，做法详见洛谷 P2697 宝石串的题解。emmm 你拿去考验 GPT 也可以。
C++ 代码：
#include<iostream>
using namespace std;
string s;
int ans,p[2000005],last=1000000;
int main()
{
cin>>s;
for(int i=1;i<=s.length();i++){
if(s[i-1]=='+')last++;
else last--;
if(p[last]==0)p[last]=i;
else ans=max(ans,i-p[last]);
if(last==1000000)ans=i;
}
cout<<ans<<endl;
return 0;
}
Python 代码：
#这是 GPT 翻译的 Python 代码，当然你让它直接写也问题不大
s = input()
ans = 0
p = [0] * 2000005
last = 1000000
for i in range(1, len(s) + 1):
if s[i - 1] == '+':
last += 1
else:
last -= 1
if p[last] == 0:
p[last] = i
else:
ans = max(ans, i - p[last])
if last == 1000000:
ans = i
print(ans)
G.打CF
下面是英文题面的翻译：
回文是一个字符串，从左到右和从右到左读出来一样。例如，abacaba、aaaa、abba、racecar 都是回文。
您将得到一个由小写拉丁字母组成的字符串 。字符串
是一个回文。
你必须检查是否有可能重新排列其中的字母以获得另一个回文（不等于给定的字符串 ）。
输入
第一行包含单个整数
——测试用例的数量。
每个测试用例的唯一一行包含一个字符串
由小写拉丁字母组成的。这个字符串是回文。
输出
对于每个测试用例，如果可以重新排列给定字符串中的字母以获得另一个回文，则打印 YES。 否则，打印 NO。
如果你只会 Python，那么题目给的代码应为：
t = int(input())
for _ in range(t):
s = input().strip()
n = len(s)
st = set(s[:n//2] if n % 2 else s[:n//2+1])
print("YES" if len(st) != 1 else "NO")
下面是该题的解：
显然，一个回文串的字符可以重新排列成一个新回文串的前提是，除了最中心的那个字符（偶回文串没有最中心字符），两边的字符不能都一样。
例如，长度为奇数的情况：“阿巴阿巴阿” 可以重新排列成 “巴阿阿阿巴”，但是“阿阿巴阿阿”，无法重排成一个新的回文串，“牛牛牛”（假设你正在采访一个某次高考提前走出来的考生）甚至一个新字符串都排不出来；
长度为偶数的情况：“香汗薄衫凉凉衫薄汗香”，显然可以再组成一个回文串，而“蹦蹦蹦蹦”，也是甚至一个新的字符串都排不成。
所以题面给出来的代码是正确的，你只需输出 个 "YES"。（果然人与人的体质是不能一概而论的，EotUL8d7 曾经一急之下，写出了正确代码）
注：
这是一道阅读题，你需要会看 C++ 程序/伪代码和英文题面。对只会 Python 和 C语言，且看代码比较少，或者没接触过英文题面的人都不太友好。
会的不用教，不会的直接教，教不会。
C++ 代码：
#include<cstdio>
int main()
{
int t;scanf("%d",&t);
while(t--)puts("YES");
return 0;
}
Python 代码：
for i in range(int(input())):
print("YES")
等高线地图
两层循环判断两个多边形是否是相互包含的，你只需输出不被任何其他多边形包含的最内层多边形的深度，这个深度就等于包含这个多边形的外层多边形的数目。
注：
- 本题数据全靠手撸。-
- 本题不是一个图论问题，不需要建一个 DAG 图再求深度。
C++ 代码：
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
int n;scanf("%d",&n);
vector<vector<pair<int,int>>> P(n);
vector<int> ans,floor(n);
vector<bool> isout(n);
for(auto&i:P)
{
int k;scanf("%d",&k);
while(k--)
{
int x,y;scanf("%d%d",&x,&y);
i.emplace_back(x,y);
}
i.push_back(i[0]);
}
for(int i=0;i<n;i++)for(int j=0;j<n;j++)if(i!=j)
{
auto&P1=P[i],&P2=P[j];
#define x first
#define y second
for(int k=1;k<P1.size();k++)
if(1ll*(P1[k-1].x-P2[0].x)*(P1[k].y-P2[0].y)<=
1ll*(P1[k].x-P2[0].x)*(P1[k-1].y-P2[0].y))
goto end;//找到反例，跳出
isout[i]=1,floor[j]++;//式子全成立，P1 包含 P2
end:;
#undef x
#undef y
}
for(int i=0;i<n;i++)if(!isout[i])ans.push_back(floor[i]+1);
sort(ans.begin(),ans.end());//从小到大排序
for(auto i:ans)printf("%d ",i);
return 0;
}
Python3 代码（不做解释）：
n=int(input())
p=[list(map(int,input().split()))[1:] for i in range(n)]
for i in range(len(p)):p[i]+=[p[i][0],p[i][1]]
floor=[1 for i in range(n)]
isout=[0 for i in range(n)]
for i in range(len(p)):
for j in range(len(p)):
if i!=j:
flag=1
x0=p[j][0]
y0=p[j][1]
for l in range(len(p[i])//2-1):
if(p[i][2*l]-x0)*(p[i][2*l+1+2]-y0)<=(p[i][2*l+2]-x0)*(p[i][2*l+1]-y0):
flag=0
break
if flag==1:
floor[j]+=1
isout[i]=1
ans=[]
for i in range(n):
if isout[i]==0:
ans.append(floor[i])
print(*sorted(ans))
I.碎片拼数
我们不急于直接想出来结果，我们先排列一下能拼出来的数看看。
容易发现，按照列对碎片重新排序后，百位的依然在百位，十位的依然在十位，个位的依然在个位，按列排列数字后结果并不变。可以进一步发现，每一列的情况都一样，而且每一个碎片会出现 次，于是我们找到对应位数的加和结果为碎片和乘以
，最后算每一位的贡献即可。
C++ 代码：
#include<cstdio>
#define mod 1000000007
int main()
{
int n,sum=0,x;scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&x),sum+=x;
int everycolumn=sum;
for(int i=1;i<=n-1;i++)everycolumn=1ll*everycolumn*i%mod;
int digit[5001];digit[0]=1;
for(int i=1;i<n;i++)digit[i]=1ll*digit[i-1]*10%mod;
int ans=0;
for(int i=0;i<n;i++)ans=(ans+1ll*digit[i]*everycolumn)%mod;
printf("%d",ans);
return 0;
}
Python 代码：
mod = 1000000007
n = int(input())
s = sum(map(int,input().split()))
everycolumn = s
for i in range(1, n):
everycolumn = (everycolumn * i) % mod
digit = [0] * n
digit[0] = 1
for i in range(1, n):
digit[i] = (digit[i-1] * 10) % mod
ans = 0
for i in range(n):
ans = (ans + digit[i] * everycolumn) % mod
print(ans)
J.一只rabbyte三十二条腿
模拟题，按照题意模拟即可。注意有很多细节/坑点。不知道各位有没有把握得住？
细节/坑点：
(1) 只 rabbyte
张嘴，
只眼睛，
条腿。
(2)，建议开 long long 或者 double。
(3)输入复数时可以用
scanf("%d%di",a,b);//或
cin>>a>>b>>c;//c 是个 char 型
Python 可以读入 complex 型，不过要先将字符串的 i 换成 j，即
zlist=list(map(complex,input().replce('i','j').split()))
(4)输出复数时，可以采用
printf("%lld%+lldi",a,b);//什么？这不是厂（删除）你不知道 %+d 是什么意思？不会用 printf？快去百度
print("%d%+di"%(z.real,z.imag),end=' ')
注：可能因为很麻烦，所以赛时很少有人过，实际并不难（大嘘），很考验基本 功，不过题面应该很有意思（确信）。
C++ 代码：
#include<cstdio>
int a[203][203],b[203][203];
int main()
{
int n,m,opt;scanf("%d%d%d",&n,&m,&opt);
char cata[10];scanf("%s",cata);
bool isbyte=cata[4]=='y';int ratio=isbyte?8:1;
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)
if(opt)scanf("%d%di",a[i]+j,b[i]+j);
else scanf("%d",a[i]+j);
//------------------------------------------------------------
for(int i=1;i<=n;i++,putchar(10))for(int j=1;j<=m;j++)
if(opt)printf("%d%+di ",a[i][j],b[i][j]);
else printf("%d ",a[i][j]);
//------------------------------------------------------------
if(isbyte)puts("rabbytes have");else puts("rabbits have");
//------------------------------------------------------------
for(int i=1;i<=n;i++,putchar(10))for(int j=1;j<=m;j++)
if(opt)printf("%d%+di ",ratio*a[i][j],ratio*b[i][j]);
else printf("%d ",ratio*a[i][j]);
//------------------------------------------------------------
puts("mouths,");
//------------------------------------------------------------
for(int i=1;i<=n;i++,putchar(10))for(int j=1;j<=m;j++)
if(opt)printf("%d%+di ",2*ratio*a[i][j],2*ratio*b[i][j]);
else printf("%d ",2*ratio*a[i][j]);
//------------------------------------------------------------
puts("eyes and");
//------------------------------------------------------------
for(int i=1;i<=n;i++,putchar(10))for(int j=1;j<=m;j++)
if(opt)printf("%lld%+lldi ",4ll*ratio*a[i][j],4ll*ratio*b[i][j]);
else printf("%lld ",4ll*ratio*a[i][j]);
//------------------------------------------------------------
printf("legs.");
return 0;
}
Python 代码：
s1=input()
s2=input()
n,m,opt=map(int,s1.split())
if opt==1:
A=[list(map(complex,input().replace('i','j').split())) for i in range(n)]
else:
A=[list(map(int,input().split())) for i in range(n)]
def output(ratio):
if opt==1:
for i in range(n):
for j in range(m):
z=ratio*A[i][j]
print("%d%+di"%(z.real,z.imag),end=' ')
print()
else:
for i in range(n):
for j in range(m):
num=ratio*A[i][j]
print(num,end=' ')
print()
output(1)
print(s2+"s have")
output(1+7*(s2=='rabbyte'))
print("mouths,")
output(2+14*(s2=='rabbyte'))
print("eyes and")
output(4+28*(s2=='rabbyte'))
print("legs.")
K.雨天与向日葵
不懂“与运算”的可以上搜索引擎上查查。OI wiki 位运算
我们可以想到，一个数字与上另一个数只能比自己小，因为可能某一位上的数字被“遮盖”掉了 （应用例如：子网掩码）。
一列数字，每个数字都是前一个数字与上另外一个数字，那么这一列数字只能
越来越小，那么这列数字最多有多少种呢？一个数字 至多有
个数字可以被
遮盖，每次都少点，这列数字中间每次被遮盖掉至少一个数字，这串数字就多一种数字，能最多遮盖
次，那么也最多只有
种数字。
这列数字可以是 ，它们中最多有
种数字。
每一个区间 ，对应一个值
，区间右端点向右移动，相等于
都同时和一个数字
进行了“与运算”，于是得到了
，并且整出来一个新数
。
于是我们可以记录下来这至多 个数字，然后每次添加新的数字和这些数字进行“与运算”，然后数数个数即可。详见代码 1（这份代码复杂度是合格的）。
另外本题有时间复杂度 的解法，其中
是输入数据的上界。
这列数字是单调递增的，且至多有
种不同的数字，我们找一个数字来代表所有和它相等的数字，每次都选择最靠后的那个来代表它这一种数字，同时记录这个数字与众不同之处，也就是他的二进制表示有一位是
但是后面那个数字对应的是
，同时记录这个数字这样独特之处的个数。
每次拓展右端点到 ，前面与众不同的数字的独特之处可能会消失，也就是它的独特之处等于
，这意味着它的独特之处被后面加入的数取代了。详见代码 2。
下面是一个印象图，不多做解释了。
C++ 代码1：
#include<set>
#include<vector>
#include<iostream>
using namespace std;
int main()
{
int n;cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i)cin >> a[i];
set<int> st[2];//两个集合交替使用
for (int i = 0; i < n; ++i)
{
st[i % 2].clear();
for (int x : st[(i + 1) % 2])
st[i % 2] .insert(x & a[i]);
st[i % 2].insert(a[i]);
cout << st[i % 2].size() << ' ';
}
return 0;
}
C++ 代码2：
#include <cstdio>
const int maxn = 2e5 + 10;
int n, a[maxn], cnt[maxn], pos[30], ans;
//cnt[i] 表示第 i 个数字最后一次被遮盖掉的数字个数
//pos[j] 表示第 j+1 位数字最后一次被遮盖掉的位置，如果等于 0 表示没有被遮盖掉
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
{
scanf("%d", a + i);
for (int j = 0; j < 30; ++j)
{
if (((a[i] >> j) & 1) == 0)//如果 a[i] 的 j+1 位数字是 0
{
if (pos[j])
{
--cnt[pos[j]];//当前数字才是最后一次被遮盖掉的数字
if (cnt[pos[j]] == 0)
--ans;//这个数字整个都被后面数字给代替了
}
++cnt[i];
pos[j] = i;//记录当前数字才是该位最后一次被遮盖掉的
}
}
++ans;//新加入的数字一定算数
printf("%d ", ans );
}
return 0;
}
Python3 代码1：
n=int(input())
a=list(map(int,input().split()))
st=(set(),set())#两个集合交替使用
for i in range(n):
st[i%2].clear()
for x in st[(i+1)%2]:
st[i%2].add(x&a[i])
st[i%2].add(a[i])
print(len(st[i%2]),end=' ')
Python3 代码2：
#注：本代码复杂度更优，但是在 CPython 解释器里运行常数过大，会超时。
#但可以选择提交 PyPy3，可以通过本题。
n=int(input())
a=[None]+list(map(int,input().split()))#[None] 占用 a[0] 的位置不然会出错
cnt=[0 for i in range(n+1)]
#cnt[i] 表示第 i 个数字最后一次被遮盖掉的数字个数
pos=[0 for i in range(30)]
#pos[j] 表示第 j+1 位数字最后一次被遮盖掉的位置，如果等于 0 表示没有被遮盖掉
ans=0
for i in range(1,n+1):
for j in range(30):
if ((a[i]>>j)&1)==0:
if pos[j]:
cnt[pos[j]]-=1#当前数字才是最后一次被遮盖掉的数字
if cnt[pos[j]]==0:
ans-=1#这个数字整个都被后面数字给代替了
cnt[i]+=1
pos[j]=i#记录当前数字才是该位最后一次被遮盖掉的
ans+=1
print(ans,end=' ')
L.挑战道馆
dp 三角型模型 过河卒和01 背包的结合。每个个点都看做 一个背包，从上面和左面一格两面转移完整的背包得来，每个背包可以加入本格的物品 （花费为格子上的数，价值为祝福值）。
C++ 代码：
#include<cstdio>
#include<algorithm>
using namespace std;
int dp[51][51][51],x;
//dp[i][j][l] 表示第 i 行第 j 列的格子上，花费 l 个道具得到的最大祝福值
int main()
{
int n,m,k;scanf("%d%d%d",&n,&m,&k);
int s[10];for(auto&i:s)scanf("%d",&i);
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)
{
scanf("%1d",&x);//%1d 读入接下来的仅仅一个数字
//继承合并上面和左面的背包
for(int l=0;l<=k;l++)dp[i][j][l]=max(dp[i-1][j][l],dp[i][j-1][l]);
//加入本背包特有的物品
for(int l=k;l>=x;l--)dp[i][j][l]=max(dp[i][j][l],dp[i][j][l-x]+s[x]);
}
int ans=0;for(int i=0;i<=k;i++)ans=max(ans,dp[n][m][i]);
printf("%d",ans);
return 0;
}
Python 代码：
n, m, k = map(int, input().split())
s = [int(x) for x in input().split()]
dp = [[[0 for _ in range(k+1)] for _ in range(m+1)] for _ in range(n+1)]
#表示第 i 行第 j 列的格子上，花费 l 个道具得到的最大祝福值
grid=[None]+[[None]+list(map(int,list(input()))) for i in range(n)]
for i in range(1, n+1):
for j in range(1, m+1):
x = grid[i][j]
#继承合并上面和左面的背包
for l in range(k+1):
dp[i][j][l] = max(dp[i-1][j][l], dp[i][j-1][l])
#加入本背包特有的物品
for l in range(k, x-1, -1):
dp[i][j][l] = max(dp[i][j][l], dp[i][j][l-x]+s[x])
print(max(dp[n][m]))
京公网安备 11010502036488号