A-做游戏
题目描述
牛牛和 牛可乐在玩石头剪刀布。
众所周知,石头剪刀布的规则是这样的:
在一局游戏中,双方各自出石头、剪刀、布其一。
胜负关系如下:
![](https://uploadfiles.nowcoder.com/images/20191203/310579_1575352167994_8E99FC0BE858ED7B25A9BC14A1A45392)
牛牛和牛可乐进行了多轮游戏,牛牛总共出了A次石头,B次剪刀,C次布;牛可乐总共出了 X次石头,Y次剪刀,Z次布。你需要求出牛牛最多获胜多少局。
输入描述
第一行,三个非负整数 A,B,C 。
第二行,三个非负整数 X,Y,Z 。
保证$ A+B+C=X+Y+Z, 0≤A,B,C,X,Y,Z≤1000000000$。
输出描述
输出一行,一个整数表示答案。
示例1
输入
114514 0 0
0 114514 0
输出
114514
思路
尽可能让牛牛的每次出 剪刀/石头/布 对应到牛可乐出 布/剪刀/石头。
ans=min(A,Y)+min(B,Z)+min(C,X)。
时间复杂度 O(1)。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
| #include<cstdio> #include<algorithm> using namespace std; int main() { long long a,b,c; long long x,y,z; scanf("%lld%lld%lld%lld%lld%lld",&a,&b,&c,&x,&y,&z); long long ans=0; ans+=min(a,y); ans+=min(b,z); ans+=min(c,x); printf("%lld",ans); return 0; }
|
B-排数字
题目描述
牛可乐最喜爱的字符串是616。
牛可乐得到了一个纯数字的字符串S,他想知道在可以任意打乱顺序的情况下,最多有多少个不同的子串为616。
当两个子串S1[l1...r1],S2=[l2...r2]满足l1=l2或r1=r2时,它们被认为是不同的。
输入描述
第一行,一个正整数 |S|,表示 S 的长度。
第二行,一个字符串 S,其字符集为 {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}。
保证 1≤∣S∣≤200000
输入描述
输出一行,一个整数表示答案。
示例1
输入
11
11451419266
输出
1
说明
一种最优打乱方案为 “11451492616”,有一个子串为 “616” 。
思路
因为字符串可以任意打乱,1和6以外不需要考虑。
要让 616子串最多一定是61616… ,这样后面的串可以用前面的6。
数量为min(cnt6−1,cnt1)(可以理解为前面一个6后面1616… 循环)
时间复杂度 O(|S|) 。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
| #include<cstdio> #include<algorithm> using namespace std; char s[200007]; int main() { int n; scanf("%d\n%s",&n,s+1); int i; int c6=0,c1=0; for(i=1;i<=n;i++) { if(s[i]=='6') c6++; else if(s[i]=='1')c1++; } int ans; ans=min(c6-1,c1); printf("%d",ans); return 0; }
|
C-算概率
题目描述
牛牛刚刚考完了期末,尽管牛牛做答了所n 道题目,但他不知道有多少题是正确的。
不过,牛牛知道第i道题的正确率是pi,牛牛想知道这n题里恰好有 0,1,…,n 题正确的概率分别是多少,对1000000007取模。
对1000000007 取模的含义是:对于一个b≠0的不可约分数 a/b,存在q 使得 b×q mod (1000000007)=a,q 即为 a/b 对1000000007取模的结果。
输入描述
第一行,一个正整数n。
第二行,n个整数 p1,p2,…,pn,在模1000000007意义下给出。
保证 1≤n≤2000。
输出描述
输出一行n+1个用空格隔开的整数表示答案(对1000000007取模)。
示例1
输入
1
500000004
输出
500000004 500000004
说明
有 1 道题,做对的概率是1/2在模1000000007意义下为 500000004 )。
思路
一道可以dp的题目,dp[i][j]表示前i题做对j题的概率,最后一次输出dp[n][j]即可。转移方程讨论的就是第j题是否做对。
需要注意的是取模意义下的概率运算。
做对的概率是p[i],那么做错的概率就是(mod+1-p[i])。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
| #include<iostream> #define N 2333 using namespace std; const int mod=1e9+7; long long dp[N][N],p[N]; int main() { ios::sync_with_stdio(false); int n; cin>>n; int i; for(i=1;i<=n;i++) cin>>p[i]; int j; dp[0][0]=1; for(i=1;i<=n;i++) { dp[i][0]=dp[i-1][0]*(mod+1-p[i])%mod; for(j=1;j<=n;j++) { dp[i][j]=(dp[i-1][j-1]*p[i]%mod+dp[i-1][j]*(mod+1-p[i])%mod)%mod; } } for(j=0;j<=n;j++) { cout<<dp[n][j]; if(j<n) cout<<' '; } return 0; }
|
D-数三角
题目描述
牛牛得到了一个平面,这个平面上有 n 个不重合的点,第i个点的坐标为 (xi,yi)。
牛牛想知道,这n个点形成的三角形中,总共有多少个钝角三角形。
输入描述
第一行,一个正整数 n,表示点数。
第二行至第 n+1 行中,第 i+1 行包含两个整数xi,yi,表示第i个点的坐标。
保证1≤n≤500,−10000≤xi,yi≤10000,任意两点不重合。
输出描述
输出一行,一个整数表示答案。
示例1
输入
3
0 0
-1145 1
1 0
输出
1
思路
这题的n给的数据范围较小,允许O(n³)的时间复杂度。直接暴力枚举,成钝角的必要条件是向量点积为负,需要用斜率不相等排除三点共线的情况。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
| #include<iostream> #define N 505 using namespace std; int x[N],y[N]; bool check(int i,int j,int k) { return (x[i]-x[k])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[k])<0&&(y[i]-y[j])*(x[j]-x[k])!=(y[j]-y[k])*(x[i]-x[j]); } int main() { ios::sync_with_stdio(false); int n; cin>>n; int i,j,k; for(i=1;i<=n;i++) { cin>>x[i]>>y[i]; } int ans=0; for(i=1;i<=n;i++) { for(j=i+1;j<=n;j++) { for(k=j+1;k<=n;k++) { if(check(i,j,k)||check(k,i,j)||check(j,i,k)) ans++; } } } cout<<ans; return 0; }
|
E-做计数
题目描述
这一天,牛牛与 牛魔王相遇了――然而这并不在牛牛期望之中。
牛魔王不出意料又给牛牛一道看似很难的题目:
求有多少个不同的正整数三元组 (i,j,k)满足i+j=k。
当两个三元组(i1,j1,k1),$ (i_2,j_2,k_2)满足i_1≠i_2或j_1≠j_2或k_1≠k_2$时,它们被认为是不同的。
输入描述
第一行,一个整数n。
保证 1≤n≤40000000。
输出描述
输出一行,一个整数表示答案。
思路
i,j为完全平方数,所以 i⋅j 为完全平方数。
令v=ij,则v2≤n。枚举v,然后找到v2的因子个数即可。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
| #include<iostream> using namespace std; int main() { ios::sync_with_stdio(false); int n; cin>>n; int i,v; int ans=0; for(v=1;v*v<=n;v++) { for(i=1;i<v;i++) { if(!(v*v%i)) ans+=2; } ans++; } cout<<ans; return 0; }
|
F-拿物品
题目描述
牛牛和牛可乐面前有n个物品,这些物品编号为1,2,…,n,每个物品有两个属性ai,bi。
牛牛与牛可乐会轮流从剩下物品中任意拿走一个,牛牛先选取。
设牛牛选取的物品编号集合为 H,牛可乐选取的物品编号的集合为T,取完之后,牛牛得分为∑ai(i∈H),牛可乐得分为∑bi(i∈T)。
牛牛和牛可乐都希望最大化自己与对方得分的差。
你需要求出两人都使用最优策略的情况下,最终分别会选择哪些物品,若有多种答案或输出顺序,输出任意一种。
输入描述
第一行,一个正整数 n,表示物品个数。
第二行,$n $个整数 a1,a2,...,an,表示 n 个物品的 A 属性。
第三行,n 个整数 b1,b2,...,bn,表示 $n 个物品的B属性。保证 2≤n≤2×10^5,0≤a≤10^9$。
输出描述
输出两行,分别表示在最优策略下牛牛和牛可乐各选择了哪些物品,输出物品编号。
示例1
输入
3
8 7 6
5 4 2
输出
1 3
2
说明
3 1
2
也会被判定为正确
思路
假设物品已经被选完,此时牛牛选择的物品A属性的价值和是N,牛可乐选择的物品B属性价值和是M 。
如果 牛牛的 (a1,b1)物品与牛可乐的 (a2,b2)换,则N′=N−a1+a2,M′=M+b1−b2,对于牛牛(目标是最大化 N-M)来说会变得更优仅当 a1+b1<a2+b2,对于牛可乐(目标也是最大化N-M)也同理。所以两人都会优先选择$ a_i+b_i最大的物品。此题重点在分差最大。牛牛每取一件物品,会得到a_i的属性,并且让牛可乐失去了b_i的属性,所以牛牛实际上得到了a_i+b_i$的属性,牛可乐的取法同理,因此,这题的思想就转变为贪心。
将物品按照两个属性的和从大到小排序,依次分给两人即可。
时间复杂度 O(nlogn)。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37
| #include<cstdio> #include<algorithm> using namespace std; struct Goods { int a,b,id; }goods[200009]; bool cmp(Goods p,Goods q) { return p.a+p.b>q.a+q.b; } int main() { int n; scanf("%d",&n); int i; for(i=1;i<=n;i++) { scanf("%d",&goods[i].a); goods[i].id=i; } for(i=1;i<=n;i++) { scanf("%d",&goods[i].b); } sort(goods+1,goods+1+n,cmp); for(i=1;i<=n;i+=2) { printf("%d ",goods[i].id); } putchar('\n'); for(i=2;i<=n;i+=2) { printf("%d ",goods[i].id); } return 0; }
|
G-判正误
题目描述
牛可乐有七个整数a,b,c,d,e,f,g并且他猜ad+be+cf=g。但牛可乐无法进行如此庞大的计算。
请验证牛可乐的猜想是否成立。
输入描述
第一行一个正整数 T,表示有 T 组数据。
每组数据输入一行七个整数a,b,c,d,e,f,g。
保证1≤T≤1000,−109≤a,b,c,g≤109,0≤d,e,f≤109。保证不会出现指数和底数同为 0 的情况。
输出描述
每组数据输出一行,若猜想成立,输出 Yes,否则输出No。
示例1
输入
2
1 1 4 5 1 4 258
114514 1919810 1 2 3 4 1
输出
Yes
No
说明
1⁵+1¹+4⁴=258
114514²+1919810³+1⁴≠1
思路
直接计算会 TLE / MLE ,考虑用快速幂在模意义下进行计算,若 ad+be+cf≡g(modM),则原式有概率成立,多选择一些模数以提高正确率。
实际情况是,取mod=1e9+7通过样例0.00%,其他取随便取一个10位数的mod基本都能过。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
| #include<cmath> #include<cstdio> #include<iostream> using namespace std; const long long mod=2368711239; long long qpow(long long a,long long b) { long long ans=1; a=a%mod; while(b) { if(b&1) ans=(ans*a)%mod; a=a*a%mod; b>>=1; } return ans; } int main() { ios::sync_with_stdio(false); int t; cin>>t; while(t--) { long long a,b,c,d,e,f,g; cin>>a>>b>>c>>d>>e>>f>>g; if((qpow(a,d)+qpow(b,e)+qpow(c,f))%mod==g%mod)cout<<"Yes"<<endl; else cout<<"No"<<endl; } return 0; }
|
H-施魔法
题目描述
牛可乐有n个元素(编号1…n),第i个元素的能量值为$ ai。牛可乐可以选择至少k个元素来施放一次魔法,魔法消耗的魔力是这些元素能量值的极差。形式化地,若所用元素编号集合为S,则消耗的魔力为max{a_i}-min{a_i}(i∈S)$。
牛可乐要求每个元素必须被使用恰好一次。
牛可乐想知道他最少需要多少魔力才能用完所有元素,请你告诉他。
输入描述
第一行两个整数n,k。
第二行n个整数a1,a2,...,an。
保证1≤k,n≤3×105,0≤ai≤109。
输出描述
输出一行,一个整数表示答案。
示例1
输入
4 2
8 7 114514 114513
输出
2
说明
使用第1、2个元素施放一次魔法,消耗魔力为8-7=1;第3、4个元素施放一次魔法,消耗魔力为114514-114513=1;两个魔法一共消耗2点魔力。
思路1
要使每个连连续区间极差之和最小,势必要将a数组从小到大排序。
令dp[i]表示用掉前i个元素的最小代价,则有:
dp[i]=mindp[j−1]+a[i]−a[j]=mindp[j−1]−a[j]+a[i],因为至少选择k个元素,于是有j∈[1,i-k+1]。于是只需要通过迭代的方式,滚动更新mindp[i−1]−a[i],就能在O(n)的时间内更新dp数组。
代码1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
| #include<iostream> #include<algorithm> #define N 300008 #define init 190283746 int dp[N]; int a[N]; using namespace std; int main() { ios::sync_with_stdio(0); int n,k; cin>>n>>k; int i; for(i=1;i<=n;i++) cin>>a[i]; fill(dp+1,dp+1+n,init); sort(a+1,a+1+n); int pre=-a[1]; for(i=k;i<=n;i++) { dp[i]=pre+a[i]; pre=min(pre,dp[i-k+1]-a[i-k+2]); } cout<<dp[n]; return 0; }
|
思路2
dp[i]就是前i个元素以i为尾划分段的最小值。
i可以是作为前一段的新尾,dp[i]=dp[i−1]−a[i−1]+a[i]。
也可是新开一段k,作为段尾 $dp[i]=dp[i-k]-a[i-k+1]+a[i] $(a[i-k+1]是头,a[i]是尾)
则动态转移方程为 dp[i]=min(dp[i−1]−a[i−1]+a[i],dp[i−k]−a[i−k+1]+a[i])。
需要注意的是1~k必须组成一个段,所以循环从 k+1 开始。
代码2
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
| #include<iostream> #include<algorithm> #define N 300008 #define init 190283746 int dp[N]; int a[N]; using namespace std; int main() { ios::sync_with_stdio(0); int n,k; cin>>n>>k; int i; for(i=1;i<=n;i++) cin>>a[i]; fill(dp+1,dp+1+n,init); sort(a+1,a+1+n); dp[k]=a[k]-a[1]; for(i=k+1;i<=n;i++) dp[i]=min(dp[i-1]-a[i-1],dp[i-k]-a[i-k+1])+a[i]; cout<<dp[n]; return 0; }
|
I-建通道
题目描述
在无垠的宇宙中,有 n 个星球,第 i 个星球有权值 vi。
由于星球之间距离极远,因此想在有限的时间内在星际间旅行,就必须要在星球间建立传送通道。
任意两个星球之间均可以建立传送通道,不过花费并不一样。第 i 个星球与第 j 个星球的之间建立传送通道的花费是lowbit(vi⊕vj)。
,其中⊕ 为二进制异或,而 lowbit(x)为x二进制最低位1对应的值,例如lowbit(5)=1,lowbit(8)=8。特殊地,lowbit(0)=0。
牛牛想在这n个星球间穿梭,于是――你需要告诉牛牛,要使这n个星球相互可达,需要的花费最少是多少。
输入描述
第一行,一个整数n。
第二行,n个非负整数v1,v2,v3,...,vn。
保证1≤n≤200000,0≤vi≤230。
输出描述
输出一行,一个整数表示答案。
思路
首先将权值去重(权值相等的点连接代价为 0),设去重后有num个点,接下来找到最小的二进制位k,满足存在vi的这个二进制位是0,且存在vj的这个二进制位是1 ,答案就是 2k×(m−1)(相当于所有这位是0的点与j点连边,是1的点与i点连边)。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34
| #include<iostream> #include<algorithm> #define ll long long using namespace std; int v[200003]; int n; int main() { ios::sync_with_stdio(0); cin>>n; int i; for(i=1;i<=n;i++) cin>>v[i]; sort(v+1,v+1+n); int num=unique(v+1,v+1+n)-(v+1); int va=v[1],vo=v[1]; for(i=2;i<=num;i++) { va&=v[i]; vo|=v[i]; } va^=vo; ll ans=0; for(i=0;i<=30;i++) { if((va>>i)&1) { ans=(ll)(num-1)*(ll)(1<<i); break; } } cout<<ans; return 0; }
|
J-求函数
题目描述
牛可乐有$ n$ 个一次函数,第i个函数为$ f_i(x)=k_i·x+b_i。牛可乐有m次操作,每次操作为以下二者其一:⋅1ikb,将f_i(x)修改为f_i(x)=kx+b。⋅2lr,求f_r(f_{r-1} (…(f_ {l+1}(f_l(1)))…))$。
牛可乐当然(bu)会做啦,他想考考你——
答案对1000000007取模。
输入描述
第一行,两个整数n,m。
第二行,n个整数k1,k2...,kn。
第三行,n个整数b1,b2,...bn。
接下来m行,每行一个操作,格式见上。
保证1≤n,m≤200000,0≤ki,bi≤1000000007。
输出描述
对于每个求值操作,输出一行一个整数,表示答案。
示例1
输入
2 3
1 1
1 0
1 2 114514 1919810
2 1 2
2 1 1
输出
2148838
2
说明
初始 f1(x)=x+1,f2(x)=x
修改后 f2(x)=114514x+1919810
查询时 f1(1)=2,f2(f1(1))=2148838
思路
又是更改,又是查询,当然是要用线段树啦。可以在O(nlogn)内完成所有查询和更新的操作。
本题为单点更新、区间查询的最基础的线段树应用,难点在于函数式的化简,化简后能找到较为清晰的递推关系。
![](https://cdn.luogu.com.cn/upload/image_hosting/1ncnr4du.png)
我们考虑如何PushUp,即合并区间[l1,r1],[r1+1,r2]。
![](https://cdn.luogu.com.cn/upload/image_hosting/ia4xc86t.png)
易得区间[l1,r2]的∏ki=n1×n2,∑bi∏kj=m1×n2+m2。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93
| #include<algorithm> #include<cstdio> #include<iostream> #define N 200001 #define ll long long using namespace std; const int mod=1e9+7; struct node { int l,r; ll k,b; }tree[N<<2]; ll k[N],b[N]; int n,m; ll ansk,ansb; void PushUp(int id) { tree[id].k=tree[id<<1].k*tree[id<<1|1].k%mod; tree[id].b=(tree[id<<1].b*tree[id<<1|1].k+tree[id<<1|1].b)%mod; return; } void build(int id,int l,int r) { tree[id].l=l; tree[id].r=r; if(l==r) { tree[id].b=b[l]; tree[id].k=k[l]; return; } int mid=l+r>>1; build(id<<1,l,mid); build(id<<1|1,mid+1,r); PushUp(id); return; } void update(int id,int pos,ll kk,ll bb) { if(tree[id].l==tree[id].r) { tree[id].k=kk; tree[id].b=bb; return; } int mid=tree[id].l+tree[id].r>>1; if(pos<=mid) update(id<<1,pos,kk,bb); else update(id<<1|1,pos,kk,bb); PushUp(id); return; } void query(int id,int l,int r) { if(l<=tree[id].l&&tree[id].r<=r) { ansk=ansk*tree[id].k%mod; ansb=(ansb*tree[id].k+tree[id].b)%mod; return; } int mid=tree[id].l+tree[id].r>>1; if(l<=mid) query(id<<1,l,r); if(r>=mid+1) query(id<<1|1,l,r); return; } int main() { scanf("%d%d",&n,&m); int i; for(i=1;i<=n;i++) scanf("%lld",&k[i]); for(i=1;i<=n;i++) scanf("%lld",&b[i]); build(1,1,n); while(m--) { short opt; cin>>opt; if(opt==1) { int pos; ll kk,bb; scanf("%d%lld%lld",&pos,&kk,&bb); update(1,pos,kk,bb); } else if(opt==2) { int l,r; ansb=0,ansk=1; scanf("%d%d",&l,&r); query(1,l,r); printf("%lld\n",(ansk+ansb)%mod); } } return 0; }
|