qw的字符串
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Problem Description
qw是杭电ACM集训队实力非常强的一位选手，他喜欢思考各种各样的算法题。qw很喜欢"belt"这个单词，希望你能在下面这个问题帮帮他。
给定一个字符串（只包含大小写字母和空格），如果包含独立的单词 "belt"（不区分大小写，不能作为某个单词的子串），则输出 "Yes"，否则输出 "No"。
Input
第一行一个正整数T，代表有T组数据。\((1 \leq T \leq 100)\)
接下来T行，每行一个字符串，只包含大小写字母和空格，其中字符串长度不大于1000。
提示：单词间可能有多个空格，也可能存在首尾空格
Output
输出T行，代表T组数据的结果。
如果字符串包含独立的单词 "belt"，输出 "Yes"。
否则输出 "No"
Sample Input
3 There iS A beLT A belt is over there I will run mybelt
Sample Output
Yes Yes No
简单题，坑点是样例中有'\t'
复杂度：\(O(n)\)
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
const int mod=(int)1e9+7;
char str[maxn];
int Isspace(int x){
return (x<'a'||x>'z')&&(x<'A'||x>'Z');
}
int len;
int check(int st){
if(str[st]=='b'){
if(str[st+1]=='e'){
if(str[st+2]=='l'){
if(str[st+3]=='t'){
if(st+4==len || Isspace(str[st+4])) return 1;
}
}
}
}
return 0;
}
void Solve(){
gets(str);
len=strlen(str);
rep(i,0,len-1) str[i]=tolower(str[i]);
rep(i,0,len-1){
if(i+3<len&&(i==0||Isspace(str[i-1]))&&check(i)){
return (void)puts("Yes");
}
}
puts("No");
}
int main() {
int cas;
scanf("%d\n",&cas);
while(cas--)Solve();
}
s10的面试
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Problem Description
s10曾经是一位ACM集训队的同学，实力强劲，秒天秒地。面临毕业的他正在找工作，最近有n个公司向s10发出了面试邀请！但s10每天只想参加一场面试。对于第i个公司的面试，会有一个最晚面试时间\(t_i\)，s10心中对于这个公司也会有一个自己的打分\(s_i\)。
因为简历投的多，s10拥有大量的面试机会，现在s10希望通过合理安排面试，使得参与面试的公司总分最大，你能帮帮他吗？
提示：
1. 可以面试的最早时间为第1天，最晚时间为第n天。
2. 对于第i个公司，如果错过了最晚面试时间\(t_i\)，即第\(t_i+1\)天及以后，则不能再参加该公司的面试。
3. 每天最多只能选择参加一场面试，每场面试均能当天结束，不会影响后面天数的选择。
Input
多组数据
每组数据第一行一个正整数n \((n \leq 1000)\)
接下来n行，每行2个正整数\(t_i\), \(s_i\)\( (1 \leq t_i,s_i \leq 1000)\)
Output
每组数据输出占一行，输出s10的最大总分
Sample Input
7 4 20 2 60 4 70 3 40 1 30 4 50 6 10
Sample Output
230
中档题，贪心，从s降序开始选择，对于一个公司选择可以去的时间中最靠后的（因为往后不会使得答案更差，时间越靠前可以选择的公司就越多），注意多组；
复杂度：\(O(nlog(n))\)
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
const int mod=(int)1e9+7;
int n;
struct node{
int s,t;
bool operator<(node b)const{return s>b.s;}
}q[maxn];
int vis[maxn];
void solve(){
int mx=0;
rep(i,1,n){
scanf("%d%d",&q[i].t,&q[i].s);
mx=max(mx,q[i].t);
}
rep(i,1,mx) vis[i]=0;
sort(q+1,q+1+n);
ll res=0;
rep(i,1,n) dep(j,q[i].t,1) if(!vis[j]){
vis[j]=1;res+=q[i].s;break;
}
printf("%lld\n",res);
}
int main() {
while(~scanf("%d",&n)) solve();
}
s10的游戏王卡牌
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Problem Description
最近s10迷上了一款叫《游戏王》的卡牌游戏，简单的介绍一下这一款游戏的规则：
1. 卡牌分成魔法卡和怪兽卡两种
2. 魔法卡能直接摧毁对方场上的一只怪兽
3. 怪兽卡拥有攻击力A和星级S
4. 每回合玩家可以将手牌中的一只怪兽召唤到场上，召唤方式有三种：
4.1. 直接召唤一只4星级及以下的怪兽
4.2. 牺牲一只己方场上的怪兽，召唤一只5-6星级的怪兽
4.3. 牺牲两只己方场上的怪兽，召唤一只7-8星级的怪兽
5. 已经被召唤的怪兽将从手牌中扣除，被破坏/牺牲的场上怪兽将会被移出游戏
s10向卡牌大师qw发起了挑战，s10手中有n张怪兽卡，第i只怪兽的攻击力为Ai，星级为Si，而qw手中有m张魔法卡。qw对s10这个新手很不屑，并表示在前k回合里他都不会使用魔法卡。而在k回合后，qw会一口气用掉所有魔法卡，破坏掉s10场上攻击力最高的m个怪兽。
而s10的任务就是在前k回合合理召唤怪兽，使得qw用掉魔法卡后，己方场上剩余的怪兽中攻击力最高的那只的攻击力尽量大
请问如果s10足够聪明，那么那只剩余下来后攻击力最高的怪兽的攻击力是多少？(如果s10所有怪兽都会被破坏/牺牲，那么输出0)
Input
多组输入
每组数据第一行给定正整数n,m,k
接下来n行，每行两个整数\(A_i\)和\(S_i\)
数据范围:
\(0 \leq A_i \leq 50000\)
\(1 \leq S_i \leq 8\)
\(1 \leq n,m \leq 100\)
\(k \leq 120\)
Output
对于每个测试实例，请输出s10最后攻击力最高的怪兽的攻击力，每个实例的输出占一行。
Sample Input
6 2 10 500 1 500 1 1500 4 900 2 2000 5 3000 7 3 2 5 500 1 700 2 1900 5 3 2 2 500 1 700 2 700 3 3 1 2 500 1 700 2 700 3
Sample Output
1500 0 0 700
中档题，暴力枚举前两种牌放的个数，第三种牌就是m+1-i-j个（因为要求的是第m+1大的牌的最大值），判掉不合理的情况就知道最小值了；
复杂度：\(O(n^2)\)
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
const int mod=(int)1e9+7;
vector<int> a,b,c;
int n,m,k;
int main(){
while(~scanf("%d %d %d",&n,&m,&k)){
a.clear(); b.clear(); c.clear();
for(int i=1,j,p;i<=n;++i){
scanf("%d %d",&j,&p);
if(p<=4) a.pb(j);
else if(p<=6) b.pb(j);
else if(p<=8) c.pb(j);
}
int ans=0;
sort(a.begin(),a.end());
sort(b.begin(),b.end());
sort(c.begin(),c.end());
for(int i=0;i<=a.size();++i){
for(int j=0;j<=b.size();++j){
int p=m+1-i-j; //第三种牌的数量
if(p*2+j*1+i>a.size()) continue;
if(p*3+j*2+i>k) continue;//放一个p要3回合，j同理
if(p<0||p>c.size()) continue;
int q=mod;
if(i) q=min(q,a[a.size()-i]);
if(j) q=min(q,b[b.size()-j]);
if(p) q=min(q,c[c.size()-p]);
ans=max(ans,q);
}
}
printf("%d\n",ans);
}
}
s10的加号求和
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Problem Description
给定一个长度为n的数字字符串，现在有m个加号需要被插入到这个字符串里，使其成为一个合法的表达式。
请求出所有的合法表达式的运算结果之和！因为数据量太大，最后结果只需要对1000000007取模输出就行。
合法表达式的规则如下：
1. 加号不能被放在开头或结尾。
2. 两个加号之间至少要有一个数字。
举例：给定字符串"50050"，加号数量为2，那么，"5+00+50", "50+0+50"等均合法的，但 "500++50", "+500+50", "500+50+"这些是非法的。
Input
多组数据。
每组数据有两行，第一行有两个整数n和m\( (0 \leq m < n \leq 10^5)\)，第二行为长度为n的数字字符串。
Output
每组数据输出一行，输出所有的合法表达式的运算结果的总和。因为结果太大，只需要输出答案对1000000007取模输出即可。
Sample Input
3 1 108 3 2 108 5 3 10008 3 0 100
Sample Output
27 9 45 100
题解：
这是本场比赛最难的题；
考虑算每个\(a_i\)产生的贡献，分成两种。
一种是\(a_i\)后面没有\(+\)的贡献\(f_i\)，\(f_i=a_i \cdot 10^{n-i} \cdot C_{i-1}^{m}\)。其中\(C_{i-1}^{m}\)是\(+\)全放在\(a_i\)前面的方案数。
另一种是\(a_i\)后面放了\(+\)的贡献\(g_i\)，那么这种情况下\(a_i\)贡献的值由他后面最近的\(+\)决定。
我们尝试去枚举这个\(+\)的位置，假设这个\(+\)插在\(a_j\)后面，,显然确定下这个\(+\)的位置后只需将剩余的\(m-1\)个\(+\)填在\(a_i\)之前或\(a_{j+1}\)之后即可，此时产生的贡献为\(a_i \cdot 10^{j-i} \cdot C_{(i-1)+(n-j-1)}^{m-1}\)，其中\(j\in[i,n-1]\)。
令\(r=j-i+1\le n-i\)。
那么我们可以发现\(g_i\)是一个类似\(g_i=a_i(10^0 \cdot C_{n-2}^{m-1}+10^1 \cdot C_{n-3}^{m-1}+ \dots +10^{r-1} \cdot C_{n-1-r}^{m-1})\)的式子。
其中\(n-1-r\ge m-1\)，\(r\le n-m\)。
结合一下就得到了\(r=\min(n-m,n-i)\)。
令\(k_i=10^{i-1}C_{n-1-i}^{m-1}\)，则\(g_i=a_i\sum_{j=1}^{\min(n-m,n-i)}k_i\)。
显然\(k_i\)的值和前缀和我们可以\(O(n)\)预处理（不会求的同学补一下乘法逆元和组合数相关知识嗷）。
那么只要\(O(n)\)遍历\(a_i\)计算出每个\(a_i\)的贡献\(f_i+g_i\)了，总复杂度\(O(n)\)。
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
const int mod=(int)1e9+7;
ll f[maxn],g[maxn],bs[maxn],k[maxn];
char s[maxn]; int a[maxn],n,m;
ll qpow(ll x,ll p){
ll res=1;
while(p){
if(p%2==1) res=res*x%mod;
x=x*x%mod; p>>=1;
}
return res;
}
ll C(int n,int m){
return f[n]*g[n-m]%mod*g[m]%mod;
}
void init(){
f[0]=1; bs[0]=1;
for(int i=1;i<maxn;++i) f[i]=f[i-1]*i%mod;
g[maxn-1]=qpow(f[maxn-1],mod-2);
for(int i=maxn-2;i>=0;--i) g[i]=g[i+1]*(i+1)%mod;
for(int i=1;i<maxn;++i) bs[i]=bs[i-1]*10%mod;
}
void solve(){
scanf("%s",s+1); ll ans=0; k[0]=0;
if(m==0){
ll tmp=0;int len=strlen(s+1);
rep(i,1,len) tmp=(tmp*10+s[i]-'0')%mod;
printf("%lld\n",tmp);return;
}
rep(i,1,n-m){
k[i]=bs[i-1]*C(n-1-i,m-1)%mod;
k[i]+=k[i-1]; k[i]%=mod;
}
rep(i,1,n) a[i]=s[i]-'0';
for(int i=n;i>m;--i) ans+=a[i]*bs[n-i]*C(i-1,m)%mod;
rep(i,1,n) ans=(ans+a[i]*k[min(n-m,n-i)])%mod;
printf("%lld\n",ans);
}
int main(){
init();
while(~scanf("%d%d",&n,&m)) solve();
}
77姐的保研之路
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Problem Description
77姐已经大三了，表示不能向菜鸡czy学习，要向杭电优秀学子dxh学习，保研清华。竞争保研资格需要计算每位同学的保研分数，择高录取，其计算方法为：
保研分数 = 平均学分绩点 * 100 + 专业课平均分 * 0.7 + 竞赛加分 * 0.2 + 综合素质分。
现在给定77姐每门课的情况（课程分数，课程学分，是否为专业课）、竞赛加分、综合素质分和今年的保研录取分数线，计算77的保研分数能否成功保研（保研分数大于等于录取线分数）？如果能，输出"Yes"，否则输出"No"。
说明：
1. 专业课平均分为所有专业课的总分数除以专业课数量。
2. 平均学分绩点的计算方式为：将所有课程分数（百分制）转换为绩点（满绩点5.0），对所有课的绩点乘以其学分权重的乘积求和，再除以总学分。
举例：比如你一共修了两门课，一门是程序设计基础，绩点是4.5，学分是4。一门是体育课，绩点是3，学分是1。那么你的平均学分绩点是：\(（4.5*4+3*1）/（4+1）=4.2\)
其中课程分数与绩点的转换关系如下：
95-100分：5.0
60分及以上且94分及以下则计算方式为：假设分数为X，则绩点为\((X - 45) / 10\)。例如：分数为94分，则绩点为\(（94-45）/10=4.9 \)
Input
第一行给出一个正整数T，表示数据组数。
每组数据，第一行给出两个正整数n和K，分别表示77姐的课程的数量和保研录取分数线。
接下来n行，每行给出三个正整数x,y,z，分别表示课程分数，课程学分和是否是专业课（z=1表示当前课程是专业课程，z=0表示为普通课程）。
随后一行两个非负整数u，v，分别代表77姐的竞赛加分和综合素质分数。
专业核心课的数量保证至少为1，保证77姐无不及格的课程。
数据范围：
\(n \leq 100;K \leq 600;60 \leq x \leq 100;y \leq 5;u \leq 100,v \leq 10\)
\(z=0或1\)
Output
对于每组数据，如果77姐能保研输出 "Yes"，否则输出 "No"。
Sample Input
3 2 500 90 4 1 75 1 0 50 10 2 510 90 4 1 75 1 0 50 10 2 510 90 4 1 80 1 0 50 10
Sample Output
Yes No Yes
简单题，模拟即可；
复杂度：\(O(n)\)
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
const int mod=(int)1e9+7;
double fun(int x){
if(x>=95) return 5.0;
return (x-45)*1.0/10;
}
void solve(){
int n,k;scanf("%d%d",&n,&k);
int sum=0,num=0;
double sum1=0,num1=0;
rep(i,1,n){
int x,y,z;scanf("%d%d%d",&x,&y,&z);
if(z==1){
sum+=x;num++;
}
sum1+=fun(x)*y;num1+=y;
}
int u,v;scanf("%d%d",&u,&v);
double ans=sum*1.0/num*0.7+sum1/num1*100+u*0.2+v;
puts(ans>=k?"Yes":"No");
}
int main(){
int T;cin>>T;
while(T--) solve();
}
s10的红黑树
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Problem Description
众所周知，红黑树是一种优秀的数据结构，是每个节点都带有颜色属性（红色或者黑色）的二叉查找树。这道题也是关于树上的问题，但是与之不同的是，是每条边有颜色属性，其值为红色或者黑色。
现在有一棵树（无环的无向图），树上有n个节点，n−1条无向边，每条边是红色或者黑色。同时给定一个正整数k，我们定义序列 \(a_1,a_2,\dots,a_k\)为 "s10序列"当且仅当其满足以下条件：我们从节点\(a_1\)开始选择最短的路径到节点\(a_2\)，再从节点\(a_2\)开始选择最短的路径到节点\(a_3\)，依次类推，直到我们从节点\(a_k−1\)走到节点\(a_k\)。如果我们走过的所有路径中经过的边，有至少一条黑色边的话， 那么就称其为”s10序列”。（注意其中对于序列中的不同\(a_i\)的取值可以重复）
显然对于n个节点的树，给定正整数k，我们可以有\(n^k\)个序列。我们现在需要统计其中有多少序列是“S10序列”。答案可能会很大，请输出答案对1000000007取模的结果。
Input
第一行给出一个正整数T，表示数据组数。
接下来对于每组数据，第一行给出两个正整数n和k，分别表示这棵树的节点个数和“S10序列”的长度。
接下来n−1行，每行给出三个正整数x,y,v，分别表示树中一条边的两个节点和边的颜色（0表示红色，1表示黑色）。
数据范围：
\(k \leq n \leq 2 \cdot 10^5\)
\(1 \leq x,y \leq n\)\( (x \neq y)\)
\(v=0或1\)
Output
对于每组数据，输出“s10序列”的数量对1000000007取模的结果。
Sample Input
3 4 4 1 2 1 2 3 1 3 4 1 2 2 1 2 1 3 2 1 2 1 3 2 0
Sample Output
252 2 4
中档题，直接求有困难那就减去不符合条件的，什么是不符合条件的呢，就是路径中全都是红色边的方案，那么我们只需要一开始对所有红色边建图，算出所有连通块的size，把答案减去所有的\(size^k\)就好了；
复杂度：\(O(n)\)
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
const int mod=(int)1e9+7;
vector<int> G[maxn];
void addedge(int u,int v){
G[u].pb(v),G[v].pb(u);
}
int vis[maxn];
void dfs(int x,int _fa,int &siz){
vis[x]=1,siz++;
for(auto v:G[x]) if(v!=_fa) dfs(v,x,siz);
}
ll qpow(ll a,ll b){
ll ret=1;
for(;b;b>>=1,a=a*a%mod) if(b&1)ret=ret*a%mod;
return ret;
}
void solve(){
int n,k;scanf("%d%d",&n,&k);
rep(i,1,n) vis[i]=0,G[i].clear();
rep(i,1,n-1){
int u,v,w;scanf("%d%d%d",&u,&v,&w);
if(!w) addedge(u,v);
}
ll res=qpow(n,k);
rep(i,1,n) if(!vis[i]){
int siz=0;
dfs(i,0,siz);
res=(res-qpow(siz,k)+mod)%mod;
}
printf("%lld\n",res);
}
int main(){
int T;cin>>T;
while(T--) solve();
}
77姐的子串
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Problem Description
77姐特别喜欢字符串！而且特别喜欢数字"8"!作为新生班助，她要交给新生们一个任务，让他们在给定的数字串中，数一数有多少这个数字串的子串，满足条件：该子串所表示的数，是8的倍数。（小提示：8的倍数满足除以8的余数为0）
其中保证数字串不含数字 "0"，只含数字 "1"~"9"。
注：子串指字符串中连续若干个字符组成的字符串。
如 "abc"的所有子串为"a","b","c","ab","bc","abc"。
而数字串的每一位都是一个数字。
Input
第一行给定一个整数T，表示有T组数据。
对于每组数据，给出一个数字字符串s。（仅包含数字1-9）
数据范围：
\(T \leq 10\)
\(|s| \leq 2000\)
|s|指字符串s的长度
Output
对于每组数据，输出一个整数，表示满足题目条件的该数字串的子串的数量。
Sample Input
4 1234 1888 8 88
Sample Output
0 7 1 3
简单题，暴力就好了，唯一考点就是边乘边取模；
复杂度：\(O(n^2)\)
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
const int mod=(int)1e9+7;
char s[2200];
int len;
void solve(){
int ans=0;
scanf("%s",s+1);
len=strlen(s+1);
rep(i,1,len){
int tmp=0;
rep(j,i,len){
tmp=(tmp*10+(s[j]-'0'))%8;
if(tmp%8==0) ans++;
}
}
printf("%d\n",ans);
}
int main(){
int T;cin>>T;
while(T--) solve();
}
qw的粉丝
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Problem Description
qw是全民K歌的知名歌手，在杭电有着众多的粉丝。某一天，qw想要正式成立自己的粉丝后援会，需要招收管理人员，于是他在杭电表白墙上发布了信息。一共有n个人报名面试。
面试必须按照报名的顺序依次进行。qw可以选择在面试完若干个粉丝以后，在所有已经面试过的粉丝中任意挑选，组建粉丝后援会管理团队。
但qw对于管理团队有着一个奇怪的要求，他希望组建的团队至少有m名粉丝，且这些粉丝的最高身高和最低身高之差不超过k个长度单位。
现在已知粉丝的身高信息，qw至少要面试多少个粉丝才能在已经面试过的粉丝中选出不少于m个人组建管理团队。
Input
第一行一个整数T，表示有T组输入数据。 \((T \leq 10)\)
每组数据第一行3个整数n,m,k，意义见题面描述，其中 \(1 \leq m \leq n \leq 10^5;0 \leq k \leq 10^5\)
第二行n个整数，第i个整数hi表示第i个报名面试的粉丝身高。\(1 \leq hi \leq 10^5\)
Output
如果可以选出管理团队，输出最少需要面试的人数。否则输出 "impossible"
Sample Input
1 6 3 5 170 169 175 171 180 175
Sample Output
4
中档题，二分答案，很多人在check时会排序，这样显然会TLE，我们用到类似哈希的方法，check时判断的是某个身高范围内的人数是否大于等于m；
复杂度：\(O(nlog(n))\)
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e6+100;
const int mod=(int)1e9+7;
int n,m,k;
int max_height=0,sum[maxn],h[maxn];
int check(int mid){
rep(i,1,max_height) sum[i]=0;
rep(i,1,mid) sum[h[i]]++;
rep(i,1,max_height) sum[i]+=sum[i-1];
rep(i,1,max_height){
int up=min(i+k,max_height);
if(sum[up]-sum[i-1]>=m) return 1;
}
return 0;
}
void solve(){
scanf("%d%d%d",&n,&m,&k);
max_height=0;
rep(i,1,n){
scanf("%d",&h[i]);
max_height=max(max_height,h[i]);
}
int l=1,r=n,ans=-1;
while(l<=r){
int mid=(l+r)>>1;
if(check(mid)) ans=mid,r=mid-1;
else l=mid+1;
}
if(~ans) printf("%d\n",ans);
else puts("impossible");
}
int main(){
int T;cin>>T;
while(T--) solve();
}
qw的异或游戏
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Problem Description
qw发明了一个有趣的异或游戏：
游戏会给定n个非负整数，第i个数的值为ai，另外给定一个非负整数m，如果能找到任意一个非负整数k，满足：
$$(a_1 \oplus k)+(a_2 \oplus k)+...+(a_n \oplus k) \leq m$$
则称该异或游戏是完美的。
现在qw的问题是，对于一个异或游戏，如果它是完美的游戏，那么k最大可以为多少？如果不存在合法的k，则输出-1。
提示：异或(\(\oplus\))是一种位运算，两个数异或，应先将两个数转成二进制，从低到高，按位运算，如果当前位两个数不同，则值为1，否则为0。
Input
第一行给定一个整数T，表示有T组数据。
每组数据有两行，第一行有两个整数n,m，意义见题目描述，第二行有n个整数，第i个整数的值为ai。
数据范围：
\(1 \leq T \leq 10\)
\(1 \leq N \leq 1000\)
\(0 \leq M \leq 10^6\)
\(0 \leq A_i \leq 1000\)
Output
对于每组数据，输出k的最大值，如果不存在合法的k，则输出-1
Sample Input
4 3 27 8 2 4 4 45 30 0 4 11 1 0 100 6 2 5 5 1 5 1 0
Sample Output
12 14 100 -1
简单题，这道题其实出锅了，之前的数据范围是1e6，但是因为数据太水了有些人暴力跑过了，出题人为了不让那部分暴力的同学心态崩就选择了改小数据让这道题变成一道签到题；
n=1000解法：暴力枚举所有的k，复杂度:\(O(nm)\)
正解：从最高位枚举答案的每一位，暴搜；复杂度:\(O(nlog(max(a))+m)\)
暴力：
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
const int mod=(int)1e9+7;
int n,m,a[maxn];
int fun(int k){
int ans=0;
rep(i,1,n) ans+=(a[i]^k);
return ans;
}
void solve(){
scanf("%d%d",&n,&m);
int ans=-1;
rep(i,1,n) scanf("%d",&a[i]);
rep(i,1,(int)1e5) if(fun(i)<=m) ans=i;
printf("%d\n",ans);
}
int main(){
int T;cin>>T;
while(T--) solve();
}
正解：
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
const int mod=(int)1e9+7;
int a[41],b[41],n,m;
ll ans=-1;
void dfs(int i,ll tmp,ll sum){
if(sum>m) return;
if(i==-1) ans=max(ans,tmp);
if(i>=0){
dfs(i-1,tmp+b[i],sum+b[i]*(n-a[i]));
dfs(i-1,tmp,sum+b[i]*a[i]);
}
}
void solve(){
scanf("%d%d",&n,&m);
ans=-1; memset(a,0,sizeof(a));
rep(i,1,n){
int x;scanf("%d",&x);
int cnt=0;
while(x){
if(x&1) a[cnt]++;
x/=2;cnt++;
}
}
dfs(20,0,0);
printf("%lld\n",ans);
}
int main(){
b[0]=1;
rep(i,1,31) b[i]=b[i-1]<<1;
int T;cin>>T;
while(T--) solve();
}
s10的卡片
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Problem Description
s10现在有n张相同的卡片，卡片的值均为m \((1 \leq m \leq 9)\) 。现在s10想用这些卡片拼成一个新的数（可以只取一部分），并希望这个数能被9整除。如果能，请输出最大可以拼成的数，否则输出"-1"。
举例：如果有8张值为6的卡片，可以：
1. 取3张拼成666，可以被9整除
2. 取6张拼成666666，可以被9整除
因为取6张的值大于取3张的值，故输出666666
Input
第一行，给出一个正整数T,表示数据组数。
接下来对于每组数据，给出两个正整数n 和 m ，分别表示卡片的张数和卡片上的数字。
取值范围：
\(1 \leq n \leq 1000\)
\(1 \leq m \leq 9\)
Output
对于每组数据，输出一个整数，表示用这些卡片最大可以拼成的被9整除的数。如果不能，则输出 “-1”。
Sample Input
4 9 5 1 2 10 2 4 3
Sample Output
555555555 -1 222222222 333
简单题，考点是边乘边取模；
复杂度：\(O(n)\)
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
const int mod=(int)1e9+7;
void solve(){
int n,m;scanf("%d%d",&n,&m);
int tmp=0,ans=0;
rep(i,1,n){
tmp=tmp*10%9+m;
if(tmp%9==0) ans=max(ans,i);
}
if(ans==0) puts("-1");
else{
rep(i,1,ans) printf("%d",m); puts("");
}
}
int main(){
int T;cin>>T;
while(T--) solve();
}
zls强强强 qwq
巨佬%%%
这位就是team240 ak巨佬