A
题目描述
牛可乐发明了一种n面骰子（点数分别从1到n，掷出每面的概率为1/n)
去给牛牛玩，因为牛牛是个欧皇，所以他想测试一下牛牛的人品，他告诉牛牛，让牛牛投m{}m次骰子，牛牛如果全部投出点数为{}nn的面就算牛牛赢，牛牛很相信自己的人品，就和牛可乐赌一包辣条，说自己肯定可以全部投出点数为{}nn点面，但是牛牛又有点害怕自己打赌输了，想让你提前帮他计算一下他输概率有多少？
思路：暴力算，逆元。
代码：
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
inline int read()
{
int X=0; bool flag=1; char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') flag=0; ch=getchar();}
while(ch>='0'&&ch<='9') {X=(X<<1)+(X<<3)+ch-'0'; ch=getchar();}
if(flag) return X;
return ~(X-1);
}
long long quickpow(long long a, long long b) {
if (b < 0) return 0;
long long ret = 1;
a %= mod;
while(b) {
if (b & 1) ret = (ret * a) % mod;
b >>= 1;
a = (a * a) % mod;
}
return ret;
}
long long inv(long long a) {
return quickpow(a, mod - 2);
}
int main()
{
int t;
t=read();
while(t--){
long long n,m;
n=read(),m=read();
long long q=quickpow(n,m);
printf("%lld\n",(q-1)*inv(q)%mod);
}
return 0;
}
B
题目描述
牛牛感觉在上一次赌约中，情况对于自己非常不利，所以决定再赌一场。
这时候，牛蜓队长出现了：第一，绝对不意气用事；第二，绝对不漏判任何一件坏事；第三，绝对裁判的公正漂亮。
牛蜓队长带他们来到了一个棋盘游戏，棋盘左上角是(0,0)(0,0)，这个棋盘在(x,y)(x,y)的位置有一个棋子，牛牛和牛可乐轮流移动这个棋子，这个棋子可以左移也可以上移，可以移动一格或者两格，直到不能再移动（即到(0,0)(0,0)）的那个人算输。
如果原本在(x,y)(x,y),左移一格即为(x,y -1)(x,y−1)，上移一格即为(x-1,y)(x−1,y)
这个时候，牛牛为了弥补上一局的不公平，决定要自己先手，如果两个人都用最优的策略，最后牛牛是否能获胜。
思路：打表发现有规律。打表就看看当前点能否到达一个先手必输点，可以的话该点先手就必胜。
代码：
#include <bits/stdc++.h>
using namespace std;
int a[3][3]={{0,1,1},{1,0,1},{1,1,0}};
int main(){
int t;
scanf("%d",&t);
while(t--){
int x,y;
scanf("%d%d",&x,&y);
if(a[x%3][y%3])printf("yyds\n");
else printf("awsl\n");
}
return 0;
}C:模拟，不想写了。
D:
题目描述
a + b的值为x，a&b的值为y，首先需要判断能否有一组a,b满足当前的情况，如果有，那么求出a xor b，否则输出-1
（其中a,b{}>0a,b>0）
思路：基本位运算。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
int t;
scanf("%d",&t);
while(t--){
long long x,y;
scanf("%lld%lld",&x,&y);
long long a=y,b=y;
x-=2*y;
for(int i=62;i>=0;i--){
if(y&(1ll<<i))continue;
if(x>=(1ll<<i))x-=(1ll<<i),a+=(1ll<<i);
}
if(x==0)printf("%lld\n",a^b);
else printf("-1\n");
}
return 0;
}G
题目描述
牛牛每天都要做的事就是读书，从书里找自己喜欢的句子，他每天都会去读一本书，如果牛牛今天读的书的某连续{}kk个字符刚好是牛牛喜欢句子的某个前缀，那么牛牛将得到{}kk点兴奋感，但他每天只能注意到一次自己喜欢的句子（也就是每天只能增加一次兴奋感），也就是说他会尽量去找那个让自己兴奋度增加最多的句子，那么，{}nn天之后牛牛总共最多能有多少兴奋感？
思路：kmp模板，找份模板，稍加修改就行了。
代码
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int nextt[100005];
void getnext(char *p)
{
int lenp=strlen(p);
nextt[0]=-1;
int k=-1;
int j=0;
while(j<lenp-1)
{
//p[k]表示前缀，p[j]表示后缀（并没有“真”！）
if(k==-1||p[j]==p[k])//j在这
{
j++;//j+1在这
k++;//k=k+1
//---->若p[k]=p[j]，则next[j+1]=next[j]+1;
//下一个位置的next
if(p[j]!=p[k])//当p[k]！=p[j]时，与主串不匹配时可以返回到这
{
nextt[j]=k;
}
else//当p[j]=p[k]时与主串匹配时你在j位置不匹配匹配串返回这里当前
//还是 不能与主串匹配，然后还是要返回next[]即next[next[k]]
nextt[j]=nextt[k];//优化了
}
else
{
k=nextt[k];
}
}
return;
}
int KMP(char *s,char *p)
{
int i=0,temp=0;
int j=0;
int lens=strlen(s);
int lenp=strlen(p);
while(i<lens&&j<lenp)
{
//如果j=-1(表示第一次开始或者重新开始匹配)，即失配于首字符
if(j==-1||s[i]==p[j])
{
j++;
i++;
temp=max(temp,j);
}
else
{
//如果j!+-1,或者当前匹配失败 ，则
j=nextt[j]; // i不变，j=next[j]
}
}
return temp;
}
int main()
{
int t;
char a[100005],b[100005];
scanf("%s",a);
getnext(a);
scanf("%d",&t);
int ans=0;
while(t--)
{
scanf("%s",b);
ans+=KMP(b,a);
}
printf("%d\n",ans);
return 0;
}
I
题目描述
有一个n×m的网格地图，每个点有个值a ij
，现在牛牛要从（1，1）走到（n，m），他可以往右边或者往下走，每次到一个点会获得当前的点权值，并将权值和mod 1e4+7，当牛牛从不同方式走到（n，m）的时候能获得多少种权值和？
思路：
判断当前点有那些权值，暴力硬算。
代码；
#include <bits/stdc++.h>
using namespace std;
bool dp[101][101][10007];
int a[101][101];
const int mod=1e4+7;
int main(){
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
scanf("%d",&a[i][j]);
a[i][j]%=mod;
}
}
dp[1][1][a[1][1]]=1;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
for(int k=0;k<mod;k++){
dp[i][j][k]|=dp[i-1][j][(k-a[i][j]+mod)%mod];
dp[i][j][k]|=dp[i][j-1][(k-a[i][j]+mod)%mod];
}
}
}
int ans=0;
for(int i=0;i<mod;i++)if(dp[n][m][i])ans++;
printf("%d\n",ans);
return 0;
}J
题目描述
牛牛苦练武功绝学——轻功水上漂，最终没有练成，但是他学会了在树上行走的本领。
这天，牛牛落入了敌人的陷阱，身后有巨石追击，面前有n个点，n-1条边连成一张连通图（一棵树），现在牛牛必须立马选择进入这张图中，但是牛牛发现，这张图有两种不同的点，一旦进入一个点，所有与该点不同类型的点都会消失（相连的边也会消失），牛牛只能走到有边相连的点，牛牛想要自己尽量有更多的点可以活动，那么他可以进入哪些点？
思路：可以按照相同点建边，然后找最大的那几个联通图，或者建边搜相同点，或者并查集找最大的块。
代码：
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
vector<int>edge[200005];
int type[200005],vis[200005];
int dfs(int u,int t)
{
vis[u]=1;
int num=0;
for(int i=0;i<edge[u].size();i++){
int v=edge[u][i];
if(vis[v]||type[v]!=t)continue;
num+=dfs(v,t);
}
return num+1;
}
vector<int>ans,ansn;
void dfs1(int u,int t)
{
vis[u]=1;
ans.push_back(u);
for(int i=0;i<edge[u].size();i++){
int v=edge[u][i];
if(vis[v]||type[v]!=t)continue;
dfs1(v,t);
}
}
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&type[i]);
}
for(int i=0;i<n-1;i++){
int u,v;
scanf("%d%d",&u,&v);
edge[u].push_back(v);
edge[v].push_back(u);
}
int num=0;
for(int i=1;i<=n;i++){
if(vis[i])continue;
int temp=dfs(i,type[i]);
if(temp>num){
ansn.clear();
ansn.push_back(i);
num=temp;
}
else if(temp==num)ansn.push_back(i);
}
memset(vis,0,sizeof(vis));
for(int i=0;i<ansn.size();i++){
//printf("%d\n",ansn[i]);
dfs1(ansn[i],type[ansn[i]]);
}
sort(ans.begin(),ans.end());
printf("%d\n",ans.size());
for(int i=0;i<ans.size();i++){
printf("%d ",ans[i]);
}
printf("\n");
return 0;
}
京公网安备 11010502036488号