牛客OI赛制测试赛3 解题报告
前话:
话说考试描述:普及难度。
于是想在这场比赛上涨点信心。
考出来的结果:Point:480 Rank:40
然而同机房的最好成绩是 510。
没考好啊!有点炸心态,D题一些细节没有注意,然后B题简单的贪心没有想到,GG~再给我30分钟我能AK!
A题:数字权重
题目描述
1. 不含前导0
2.
输入描述:
两个整数N, K 若存在无解的情况,请输出0
输出描述:
一个整数表示答案,对10
9
+ 7取模
输入
2 3
输出
6
说明
满足条件的数有:14, 25, 36, 47, 58, 69
输入
2 -3
输出
7
说明
满足条件的数有:41, 52, 63, 74, 85, 96, 30
输入
4 3
输出
600
说明
可能的方案有:1234, 1334
输入
4 -3
输出
700
备注:
对于30%的数据:n, |k| = 5
对于60%的数据:n, |k| ≤ 1000
/*Code by 520 -- 10.12*/
#include<bits/stdc++.h>
#define il inline
#define ll long long
#define RE register
#define For(i,a,b) for(RE int (i)=(a);(i)<=(b);(i)++)
#define Bor(i,a,b) for(RE int (i)=(b);(i)>=(a);(i)--)
using namespace std;
const ll mod =1e9+;
ll n,k; ll Exp(ll s,ll k){
ll ans=;
s%=mod;
while(k){
if(k&) ans=ans*s%mod;
k>>=;
s=s*s%mod;
}
return ans;
} int main(){
cin>>n>>k;
if(k>=&&k<) printf("%lld\n",1ll*(-k)*Exp(,n-)%mod);
else if(k<&&k>-)printf("%lld\n",1ll*(+k)*Exp(,n-)%mod);
else cout<<;
return ;
}
B题:毒瘤XOR
题目描述
1、
2、最大,表示异或操作(不懂的请自行百度)
输入描述:
第一行一个整数N,表示序列的长度
第二行N个整数,表示序列内的元素
第三行一个整数q,表示询问的个数
接下来q行,每行两个整数[L, R],表示询问的区间
输出描述:
输出q行,每行一个整数表示答案 若有多组可行解,请输出较小的解
输入
5
4 78 12 1 3
3
2 5
1 4
3 3
输出
2147483632
2147483635
2147483635
备注:
对于30%的数据,n , q ≤ 10
对于60%的数据,n , q ≤ 1000
/*Code by 520 -- 9.12*/
#include<bits/stdc++.h>
#define il inline
#define ll long long
#define RE register
#define For(i,a,b) for(RE int (i)=(a);(i)<=(b);(i)++)
#define Bor(i,a,b) for(RE int (i)=(b);(i)>=(a);(i)--)
using namespace std;
const int N=;
int n,m,a,sum[N][]; il int solve(int l,int r){
int tot[],num=,mid=(r-l+)/;
For(i,,) tot[i]=sum[r][i]-sum[l-][i];
Bor(i,,) if(tot[i]<mid) num+=(<<i);
return num;
} int main(){
scanf("%d",&n);
For(i,,n) {
scanf("%d",&a);
For(j,,) if(<<j&a) sum[i][j]++;
For(j,,) sum[i][j]+=sum[i-][j];
}
int l,r;
scanf("%d",&m);
while(m--){
scanf("%d%d",&l,&r);
printf("%d\n",solve(l,r));
}
return ;
}
C题:硬币游戏
题目描述
输入描述:
第一行,一个数字n(N<=1000000)
第二,三行,每行各一个长度为2n的字符串
输出描述:
一行 输出 clccle trl!或sarlendy tql!或orz sarlendy!
输入
3
UDUDUU
DUDUUD
输出
clccle trl!
说明
clccle先取5,sarlendy取4,clccle取6,sarlendy取2,clccle取1,sarlendy取3
此时clccle得到的数字为111,sarlendy得到的数字为110
因为111>110 所以说输出clccle trl!
备注:
不保证数据有梯度(但肯定没有极限数据)
Solution:
本题纯贪心模拟。
我们以$UU$表示同一位置都为$U$的个数,$Ua$表示a单独的$U$的个数,$Ub$表示b单独的$U$个数。
先判断$UU$个数奇偶的情况:
当$UU$为奇时,若$Ua>=Ub$则a赢,若$Ua+1=Ub$则平局,否则b赢。
当$UU$为偶时,若$Ua>Ub$则a赢,若$Ua==Ub$或者$Ua==0,Ub==1$则平局,否则b赢。
代码:
/*Code by 520 -- 9.12*/
#include<bits/stdc++.h>
#define il inline
#define ll long long
#define RE register
#define For(i,a,b) for(RE int (i)=(a);(i)<=(b);(i)++)
#define Bor(i,a,b) for(RE int (i)=(b);(i)>=(a);(i)--)
using namespace std;
const int N=;
int n,ua,ub,tt;
char s[N],t[N]; int main(){
scanf("%d%s%s",&n,s+,t+);
For(i,,n<<){
if(s[i]=='U'&&t[i]=='U') tt++;
else if(s[i]=='U'&&t[i]!='U') ua++;
else if(s[i]!='U'&&t[i]=='U') ub++;
}
if(tt&&&ua>=ub) puts("clccle trl!"),exit();
if(tt&&&ub-ua==) puts("orz sarlendy!"),exit();
if(tt&) puts("sarlendy tql!"),exit();
if(ua>ub) puts("clccle trl!"),exit();
if(ua==ub||!ua&&ub==) puts("orz sarlendy!"),exit();
puts("sarlendy tql!");
return ;
}
D题:粉樱花之恋
题目描述
又是一年嘤花烂漫时,小qn于是就邀请了qy去嘤花盛开的地方去玩。当qy和qn来到了田野里时,qy惊奇的发现,嘤花花瓣以肉眼可见的速度从树上长了出来。
仔细看看的话,花瓣实际上是以一定规律长出来的,而且,每次张成新的花瓣的时候,上一次的花瓣就会都落到地上,而且不会消失。
花瓣生长的规律是,当次数大于等于2时,第i次长出来的花瓣个数和上一次张出来的花瓣个数的差是斐波那契数列的第i-1项。初始的时候地上没有花瓣,树上的花瓣个数为1,第一次生长的花瓣个数为1。初始的那个花瓣就落到了地上
输入描述:
一行一个数k
输出描述:
一行一个数m,表示第k次生长过后,树上和地上的总花瓣数是多少。由于答案会很大,请你将答案mod 998244353后输出
输入
4
输出
12
说明
第一次:树上1,地上1.第二次树上2,地上1+1,第三次树上3,地上1+1+2,第四次树上5,地上1+1+2+3。总共12个
输入
5
输出
20
说明
第五次树上8,地上1+1+2+3+5。总共20个
备注:
对于0%的数据,有k=样例
对于20%的数据,有k<=1'000
对于60%的数据,有k<=1'000'000
对于80%的数据,有k<=1'000'000'000
对于100%的数据,有k<1'000'000'000'000'000'000
Solution:
本题矩阵我写挂了,只得80分。
我们观察样例,容易看出要求的是斐波那契前$k+1$项的和。
打一张表,不难发现斐波那契前缀和有递推公式,设$g[i]$表示前$i$项的和,则$g[1]=2,g[2]=4$,$g[i]=g[i-1]+g[i-2]+1$。
然后就能构造矩阵了:
初始矩阵:$\begin{bmatrix}
2& 4 & 7 & 1
\end{bmatrix}$
转移矩阵:$\begin{bmatrix}
0 & 0 & 0 & 0\\
1 & 0 & 1 & 0\\
0 & 1 & 1 & 0\\
0 & 0 & 1 & 1
\end{bmatrix}$
代码:
/*Code by 520 -- 9.12*/
#include<bits/stdc++.h>
#define il inline
#define ll long long
#define RE register
#define For(i,a,b) for(RE int (i)=(a);(i)<=(b);(i)++)
#define Bor(i,a,b) for(RE int (i)=(b);(i)>=(a);(i)--)
#define Clr(p) memset(&p,0,sizeof(p))
using namespace std;
const int mod=;
ll n;
struct matrix{ll a[][],r,c;}; il matrix Mul(matrix x,matrix y){
matrix tp;Clr(tp);
tp.r=x.r,tp.c=y.c;
For(i,,x.r-) For(j,,y.c-) For(k,,x.c-)
tp.a[i][j]=(tp.a[i][j]+x.a[i][k]*y.a[k][j]%mod)%mod;
return tp;
} il ll Exp(ll k){
if(!k) return ;
if(k==) return ;
if(k==) return ;
k-=;
matrix tp,ans;Clr(tp),Clr(ans);
ans.r=,ans.c=tp.r=tp.c=;
ans.a[][]=,ans.a[][]=,ans.a[][]=,ans.a[][]=;
tp.a[][]=tp.a[][]=tp.a[][]=tp.a[][]=tp.a[][]=tp.a[][]=;
while(k){
if(k&) ans=Mul(ans,tp);
k>>=;
tp=Mul(tp,tp);
}
return ans.a[][];
} int main(){
cin>>n;
cout<<Exp(n);
return ;
}
E题:符合条件的整数
题目描述
众所周知,某个被共青团点名的学校的机房里有一个蒟蒻,名字叫做clccle,因为文化课成绩不好而经常被班主任gank,这次他遇到了一个很困(rui)难(zhi)的数学题,因为clccle非常辣鸡,所以他想到了聪明的你,你能帮Ta解决这个问题吗?
输入描述:
一行,两个整数N,M 0<=N<M<=65
输出描述:
一个数字ans,表示满足条件的数字的个数
输入
2 3
输出
0
说明
在区间[22,23 )里满足条件的整数的个数为零 ,(4,5,6,7)8因为在开区间边界上所以不做考虑)
Solution:
本题最水,送分到位。
直接用$__int128$来存左右区间,然后求$[1,n]$中$\equiv 1\mod 7$的数$i$的个数,显然等于$\lceil \frac{n}{7} \rceil$,然后用$r-(l-1)$统计答案,稍微注意下区间的开闭就好了。
代码:
/*Code by 520 -- 9.12*/
#include<bits/stdc++.h>
#define il inline
#define ll long long
#define RE register
#define For(i,a,b) for(RE int (i)=(a);(i)<=(b);(i)++)
#define Bor(i,a,b) for(RE int (i)=(b);(i)>=(a);(i)--)
using namespace std;
int n,m;
__int128 a=,b=; int main(){
ll ans=;
cin>>n>>m;
if(!n) ans=;
For(i,,n-) a*=;
For(i,,m-) b*=;
a--,b--;
ans-=ceil((long double)a/),ans+=ceil((long double)b/);
cout<<ans;
return ;
}
F题:可爱即正义
题目描述
输入描述:
一行一个字符串s
输出描述:
如果他能通过只交换其中的两个位置上的字符使"suqingnianloveskirito"不是交换后的字符串的子串,则在第一行输出一个Yes,之后一行输出两个数d1,d2,表示你的方案是把原字符串在位置d1和位置d2上的字符互换,字符串的第一个字符的位置是1。
如果他不管交换那两个字符都不能满足条件,直接输出一行No。
输入
suqingnianloveskiritosuqingnianloveskiritosuqingnianloveskiritothemostimportantthingneedsaidatleastthreetimes
输出
No
输入
suqingnianloveskiritosomuch
输出
Yes
1 2
备注:
对于100%数据,有字符串的长度<=1000000
对于10%数据,有测试数据的答案=样例。
并且你的方案中,不能出现d1=d2的情况。
如果有多种可行方案,输出任何一种即可得分
Solution:
本题KMP板子。
我们先求出模式串的next值,然后在主串中匹配,若模式串出现次数超过2次,就无解,否则就特判一下出现0、1、2次的输出情况就好了。
代码:
/*Code by 520 -- 9.12*/
#include<bits/stdc++.h>
#define il inline
#define ll long long
#define RE register
#define For(i,a,b) for(RE int (i)=(a);(i)<=(b);(i)++)
#define Bor(i,a,b) for(RE int (i)=(b);(i)>=(a);(i)--)
using namespace std;
const int N=;
int n,m=,f[N],l1,r1,l2,r2;
char s[N],t[N]={'s','u','q','i','n','g','n','i','a','n','l','o','v','e','s','k','i','r','i','t','o'}; int main(){
scanf("%s",s),n=strlen(s);
int p=,tot=;
For(i,,m-){
while(p&&t[p]!=t[i]) p=f[p];
if(t[p]==t[i]) f[i+]=++p;
else f[i+]=;
}
p=;
For(i,,n-){
while(p&&s[i]!=t[p]) p=f[p];
if(s[i]==t[p]) p++;
if(p==m) {
tot++;
if(!l1) l1=i-m+,r1=i+;
else if(!l2) l2=i-m+,r2=i+;
else printf("No"),exit();
}
}
printf("Yes\n");
if(!l1) printf("1 2");
else if(!l2) printf("%d %d",l1,l1+);
else printf("%d %d",l1,l2+);
return ;
}
最新文章
- CH模拟赛 还教室
- 【Beta】Daily Scrum Meeting第五次
- using关键字的使用
- Marven笔记贴
- MVC5 + EF6 + Bootstrap3 (13) 查看详情、编辑数据、删除数据
- 【CodeForces】【311C】Fetch the Treasures
- JavaSE GUI显示列表 JTable的刷新 重新加载新的数据
- HDU 1043 Eight (A* + HASH + 康托展开)
- HttpWebRequest中的KeepAlive
- Wpf自定义路由事件
- poj 1088 动态规划+dfs(记忆化搜索)
- Android 学习开发笔记《Service 与 Thread 的区别 》
- python成长之路17
- mailcore -- Mail port
- POJ 1659 Frogs&;#39; Neighborhood(度序列组成)
- echo '1'.print(2)+3; 的输出结果为什么是511
- Codeforces Round #489 (Div. 2) E. Nastya and King-Shamans(线段树)
- MYSQL 文件类型
- javascript 缩写技巧
- BZOJ1916[USACO 2010 Open Gold 2.Water Slides]——DP+记忆化搜索
热门文章
- 发现一个很N且免费的html5拓扑图 关系图 生成组件
- Winfrom Panel Scroll End 的实现
- 一个IT男的表白
- 高可用OpenStack(Queen版)集群-7.Neutron控制/网络节点集群
- Codeforces Round #515 (Div. 3) 解题报告(A~E)
- webpack构建Vue项目引入jQ时发生“&#39;$&#39; is defined but never used”的处理
- [朴孝敏][Road Trip]
- tr命令详解
- Daily Scrum 1 --团队项目所需时间估计以及任务分配
- java的内存管理机制