题目描述
在acimo星球, tabris 是一名勇敢的屠龙勇士，在上绿岛屠龙前决定挑选N种装备武装自己，现在每种装备有两个，**但每种装备tabris必须选择拿一个**，**不能多也不能少**。
每件装备有自己的属性值，能给tabris属性加成。
对于不同种类的装备之间有叠加效果,如果选择多件装备,最终的属性加成为他们的乘积。
若tabris初始属性值为0，最后属性加成的期望是多少。
每件装备有自己的属性值，能给tabris属性加成。
对于不同种类的装备之间有叠加效果,如果选择多件装备,最终的属性加成为他们的乘积。
若tabris初始属性值为0，最后属性加成的期望是多少。
输入描述:
有多组测试样例，输入到文件结束。
每组测试数据的第一行包含一个正整数NN，表示装备的种类数。
接下来N行，每行两个正整数ai、bi，表示两个不同的第ii种装备的属性加成值。
N∈[1,103]
ai,bi∈[1,106]
输出描述:
对于每组测试数据输出一个整数,为了方便输出最终的结果先乘2N再对1e9+7取模后的值。
示例1
输入
4 1 2 3 4 5 6 7 8
输出
3465
说明
3465 = (1*3*5*7) + (1*3*5*8) +(1*3*6*7) + (1*3*6*8) + (1*4*5*7) + (1*4*5*8) + (1*4*6*7) + (1*4*6*8) + (2*3*5*7) + (2*3*5*8) + (2*3*6*7) + (2*3*6*8) + (2*4*5*7) + (2*4*5*8) + (2*4*6*7) + (2*4*6*8) ;
乘法定理，答案就是 [(a1+b1)*(a2+b2)*......*(an+bn)]%MOD
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define inf 0x3f3f3f3f 4 #define LL long long 5 LL MOD=1e9+7; 6 int main() 7 { 8 int n,m,i,j,k; 9 long long s,a,b; 10 while(cin>>n){ 11 s=1; 12 for(i=1;i<=n;++i) 13 { 14 scanf("%lld%lld",&a,&b); 15 a+=b; 16 s=s*a%MOD; 17 } 18 printf("%lld\n",s); 19 } 20 return 0; 21 }
tabris实在是太穷了，为了发财，tabris去买了一张彩票，幸运地中了特别奖。
特别奖是这样的，不会直接给你发钱.会给你一串二进制数s，让你在s中选择一个不大于k的区间,这个区间表示的数就是获奖者的奖金数目.
tabris中奖之后已经激动地蒙圈了,他不知道如何选择能获得最多的钱,你能帮帮他不?
输入描述:
输入一个整数T(T≤10)，代表有T组数据.
每组数据占两行.
第一行有一个整数K(k≤60),代表tabris能选择的数字区间的大小.
第二行有一个字符串s(∣s∣≤106).
保证 k≤∣s∣
输出描述:
输出一行"Case #x: y",x代表第x组数据,y代表tabris能得到的最多的钱。
示例1
输入
3 1 10101 3 10101 5 10101
输出
Case #1: 1 Case #2: 5 Case #3: 21
说明
对于第一个样例，最大结果为1，选择 [1]0101，10[1]01，1010[1] 。
对于第二个样例，最大结果是5，选择 [101]01，10[101]。
对于第三个样例，最大结果为21，选择 [10101]。
O(N)扫一遍，维护一个01串对应的十进制数，找到最大的一个就是答案。
由于错误的把ans默认为是上一个01串的值导致短路，后来发现了- -忧桑
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define inf 0x3f3f3f3f 4 #define LL long long 5 LL MOD=1e9+7; 6 char s[1000005]; 7 LL two[66]={1,2}; 8 LL getv(int l,int r) 9 { 10 LL res=0,b=1; 11 for(int i=r;i>=l;b*=2,i--) 12 { 13 res+=(s[i]-'0')*b; 14 } 15 return res; 16 } 17 int main() 18 { 19 int t,n,m,i,j,k; 20 for(LL x=2;x<=64;++x) two[x]=(LL)2*two[x-1]; 21 cin>>t; 22 for(int cas=1;cas<=t;++cas) 23 { 24 scanf("%d %s",&k,s); 25 int len=strlen(s); 26 LL ans=getv(0,k-1),las=ans; 27 for(i=1,j=k;j<len;i++,j++) 28 { 29 LL tmp=las; 30 if(s[i-1]-'0'==1){ 31 tmp-=two[k-1]; 32 } 33 tmp*=2; 34 if(s[j]-'0'==1) tmp++; 35 ans=max(ans,tmp); 36 las=tmp; 37 } 38 printf("Case #%d: %lld\n",cas,ans); 39 } 40 return 0; 41 }
C-小明打联盟
题目描述
小明很喜欢打游戏，现在已知一个新英雄即将推出，他同样拥有四个技能，其中三个小技能的释放时间和固定的伤害值为：
1.乌鸦坐飞机 释放时间：x 固定伤害值：a
2.蜘蛛吃耳屎 释放时间：y 固定伤害值：b
3.饿狼前进 释放时间：z 固定伤害值：c
他还有一个大招，其释放的时间是一个区间【L,R】，可以在区间内任意时间点释放出技能，其如果在L+i时刻释放技能，其能够打出的伤害值为:temp+A*i
这里temp值表示技能的基础伤害（同时也就是在时刻L释放技能的伤害值）,A是一个常数。
小明很喜欢研究连招使得在有限的时间内打出最高的伤害，现在他想要在T长度单位时间内打出最高的伤害，问这个最大伤害值。
输入描述:
本题包含多组数据。
输入格式为：
T
x a
y b
z c
L R temp A
数据范围：
1<=T<=1e5
1<=x,y,z,L,R<=T
L<=R
<=a,b,c,temp,A<=1e5
输出描述:
输出包含一行，输出能够打出的最高伤害值。
示例1
输入
8 3 1 2 3 1 3 3 3 3 3
输出
24
备注:
大招：蓄力时间最短L秒，最多R秒。无限次释放，释放之后照成的伤害是随着时间增加的
蓄力L秒释放能够造成Temp的伤害
蓄力L+1秒释放能够造成Temp+1*A的伤害
依次类推
题目描述很操蛋= =最后加了提示终于看懂了，线性dp+堆维护最优值。
有一个显然的递推方程 f[i]=MAX{f[i-x]+a | i>=x,f[i-y]+b | i>=y,f[y-z]+c | i>=z} //对于前三个技能而言
f[i]=MAX{f[j]+temp+A*(i-j-L) | i-R<=j<=i-L } //对于大招来说
显然对于大招的方程来说，j是有序的，也就是说对于当前的i不满足条件的f[j](因为不满足合法的范围)，对以后的i肯定也不会满足这个范围，所以我们可以直接去掉他。
那想通这里就很easy了，优先队列维护一下即可。
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define LL long long 4 LL f[100010]; 5 struct node 6 { 7 LL w; 8 int u; 9 bool operator<(const node& t)const{ 10 return w<t.w; 11 } 12 }; 13 int main() 14 { 15 int t,x,y,z,a,b,c,L,R,temp,A; 16 int i,j,k; 17 while(scanf("%d%d%d%d%d%d%d%d%d%d%d",&t,&x,&a,&y,&b,&z,&c,&L,&R,&temp,&A)!=EOF){ 18 priority_queue<node>Q; 19 Q.push(node{0,0}); 20 memset(f,0,sizeof(f));LL ans=0; 21 for(i=1;i<=t;++i) 22 { 23 if(i-x>=0){ 24 f[i]=max(f[i],max(f[i-x],f[i-x])+(LL)a); 25 } 26 if(i-y>=0){ 27 f[i]=max(f[i],max(f[i-y],f[i-y])+(LL)b); 28 } 29 if(i-z>=0){ 30 f[i]=max(f[i],max(f[i-z],f[i-z])+(LL)c); 31 } 32 if(i>=L){ 33 while(!Q.empty()&&!(Q.top().u>=i-R&&Q.top().u<=i-L))Q.pop(); 34 f[i]=max(f[i],Q.top().w+(LL)temp+(LL)A*(i-L)); 35 } 36 Q.push(node{f[i]-(LL)A*i,i}); 37 ans=max(ans,f[i]); 38 // cout<<f[i]<<endl; 39 } 40 cout<<ans<<endl; 41 } 42 return 0; 43 }
D-数圈圈
题目描述
tabris有一个习惯，无聊的时候就会数圈圈，无论数字还是字母。
现在tabris更无聊啦，晚上睡不着觉就开始数羊，从a只数到b只。
顺便还数了a到b之间有多少个圈。
但是tabris笨啊，虽然数羊不会数错，但很可能数错圈的个数。
但是tabris很难接受自己笨这个事实，所以想问问你他一共应该数出多少个圈，这样tabris才好判断他到底笨不笨啊。
输入描述:
输入一个T，表示数据组数
每组测试数据包含两个正整数a，b。
T∈[1,1000]
a,b∈[1,1014]
输出描述:
每组数据输出结果，并换行。
示例1
输入
11 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 1 100
输出
0 0 0 1 0 1 0 2 1 1 111
备注: 数字的圈的个数请根据样例自行理解。
数位dp原题。
数位dp接触不多，用之前的写法实在是恶心，，不仅丑效率低下，这个写法很帅，统计每一位数字对0~9的贡献，复杂度也很低。
对于一个数x1x2x3x4x5,我们每次枚举一位(从低到高)，统计贡献值，假设对于345这个数，百位对0~9的贡献依次是(40,40,40,40,36,30,30,30,30,30)
当j==cur的时候，贡献的数的范围就是[40,49],[140,149],[240,249],[340,345], 也就是 pre*i+after+1.
当j<cur的时候，假设j=3,贡献的数的范围就是[30,39],[130,139],[230,239],[330,339],也就是 (pre+1)*i
当j>cur的时候，假设j=7,贡献的数的范围就是[70,79],[170,179],[270,279],也就是pre*i
特别注意对于0，每次都会多算，记得减去i，f[0]-=i,因为这样就按的00，01，02，001，002都是合法的，我们要减去这些'额外的贡献'。
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define int long long 4 int f[10],n,m,ans[10]; 5 inline void work(int x,int y) 6 { 7 for (int i=1;i<=x;i*=10) 8 { 9 int cur=(x/i)%10,pre=x/(i*10),after=x-x/i*i; 10 11 for (int j=0;j<10;++j) 12 { 13 if (cur>j) 14 f[j]+=(pre+1)*i*y; 15 if (cur<j) 16 f[j]+=pre*i*y; 17 if (cur==j) 18 f[j]+=(pre*i+after+1)*y; 19 } 20 f[0]-=i*y; 21 } 22 } 23 signed main() 24 { 25 int t; 26 cin>>t; 27 while(t--){ 28 cin>>n>>m; 29 int anss=0; 30 memset(f,0,sizeof(f)); 31 memset(ans,0,sizeof(ans)); 32 work(n-1,-1); 33 work(m,1); 34 for (int x=0;x<=9;++x){ 35 if(x==4||x==0||x==6||x==9)anss+=f[x]; 36 if(x==8) anss+=(int)2*f[x]; 37 } 38 cout<<anss<<'\n'; 39 } 40 41 }