- solved 5
- A(签到)
题意: 两个人随机得到 0 或 1 其中之一数字, 每个人都可以猜对方的数字是什么, 有一个人猜对就算成功, 问最优策略下 00,01,10,11 四种情况两人的成功概率分别是多少.
题意不明的签到题, 题面说两人不能沟通, 以为就是两个人随便猜, 成功率都是 1-0.5*0.5=0.75. 结果是两个人可以提前商量好策略, 那显然可以其中一个人猜和自己相同的数, 另一个人猜和自己不同的数, 那么所有的成功率都是 100%.
- #include<bits/stdc++.h>
- using namespace std;
- #define rep(i,n) for(int i=1;i<=n;i++)
- #define LL long long
- #define pii pair<int,int>
- #define mp make_pair
- #define st first
- #define nd second
- #define pb push_back
- const int N= 1e7+7;
- const int inf= 3e3+7;
- int main(){
- printf("1.00\n1.00\n1.00\n1.00\n");
- system("pause");
- }
- View Code
- 0:48(2A)
- B(递推)
题意: 求斐波那契数列每一项的平方的连续一段和.
题意不明的签到题, 前缀和, 注意最后相减之后要加 mod 再模 mod 防止出现负数.
- #include<bits/stdc++.h>
- using namespace std;
- #define rep(i,n) for(int i=1;i<=n;i++)
- #define LL long long
- #define pii pair<int,int>
- #define mp make_pair
- #define st first
- #define nd second
- #define pb push_back
- const int N= 1e6+7;
- const int inf= 3e3+7;
- const int mod=192600817;
- int get(int a,int b){
- return a*4+b+1;
- }
- LL f[N],F[N];
- int main(){
- f[1]=f[2]=1;
- F[1]=1;
- F[2]=2;
- for(int i=3;i<=1e5;i++){
- f[i]=(f[i-1]+f[i-2])%mod;
- F[i]=f[i]*f[i]%mod;
- F[i]+=F[i-1];
- F[i]%=mod;
- }
- int q;
- while(cin>>q){
- while(q--){
- int a,b,c,d;
- cin>>a>>b>>c>>d;
- //if(get(a,b)==get(c,d))cout<<0<<endl;
- if(get(c,d)<get(a,b))cout<<(F[get(a,b)]-F[get(c,d)-1]+mod)%mod<<endl;
- else cout<<(F[get(c,d)]-F[get(a,b)-1]+mod)%mod<<endl;
- }
- }
- system("pause");
- }
- View Code
- 1:37(3A)
- C(模拟)
题意: 把一个数字变换为他的各数位的平方和, 经过若干次变换后这个数可以变成 1, 则称他为鸽子数, 求第 K 个鸽子数.
记忆化搜索即可.
- #include<bits/stdc++.h>
- using namespace std;
- #define rep(i,n) for(int i=1;i<=n;i++)
- #define LL long long
- #define pii pair<int,int>
- #define mp make_pair
- #define st first
- #define nd second
- #define pb push_back
- const int N= 1e7+7;
- const int inf= 3e3+7;
- int cnt;
- int ans[N],vis[N],mem[N],in[N];
- int solve(int x){
- if(mem[x]!=-1)return mem[x];
- if(x==1)return 1;
- if(in[x])return 0;
- in[x]=1;
- int res=x,now=0;
- while(res){
- now+=(res%10)*(res%10);
- res/=10;
- }
- mem[x]=solve(now);
- in[x]=0;
- return mem[x];
- }
- int main(){
- memset(mem,-1,sizeof(mem));
- for(int i=1;i<=2e6;i++)if(mem[i]==-1)mem[i]=solve(i);
- rep(i,2e6)if(mem[i])ans[++cnt]=i;
- int q;
- cin>>q;
- while(q--){
- int k;
- cin>>k;
- cout<<ans[k]<<endl;
- }
- system("pause");
- }
- View Code
- 0:33(1A)
- D
- E(线性代数)
题意: 给出三个点的坐标, 以及线性变换后三个点的新坐标 (保证三点不共线), 多次询问(x,y) 经过线性变换后的坐标
F
G(数学)
- #include<bits/stdc++.h>
- using namespace std;
- #define rep(i,n) for(int i=1;i<=n;i++)
- #define LL long long
- #define pii pair<int,int>
- #define mp make_pair
- #define st first
- #define nd second
- #define pb push_back
- const int N= 1e7+7;
- const int inf= 3e3+7;
- const int mod=1000000007;
- LL po(LL x){
- if(x==0)return 1;
- LL res=po(x/2);
- if(x&1)return res*res%mod*2%mod;
- return res*res%mod;
- }
- int main(){
- LL x;
- while(cin>>x){
- cout<<(x-1)%mod * (po(x)%mod) %mod +1<<endl;
- }
- system("pause");
- }
- View Code
- 1:12(1A)
- H
- I
- J(矩阵快速幂)
题意: f[n]=f[n-1]+2*f[n-2]+n^3,f[1]=1,f[2]=2, 求 f[n].
矩阵快速幂裸题
(打了好久...)
- #include<bits/stdc++.h>
- using namespace std;
- #define rep(i,n) for(int i=1;i<=n;i++)
- #define LL long long
- #define pii pair<int,int>
- #define mp make_pair
- #define st first
- #define nd second
- #define pb push_back
- const int N=6;
- const int inf= 3e3+7;
- const int mod=123456789;
- LL tmp[N][N];
- void multi(LL a[][N],LL b[][N],int n)
- {
- memset(tmp,0,sizeof tmp);
- for(int i=0;i<n;i++)
- for(int j=0;j<n;j++)
- for(int k=0;k<n;k++)
- tmp[i][j]=(tmp[i][j]+ (b[i][k]%mod*a[k][j]%mod) )%mod;
- for(int i=0;i<n;i++)
- for(int j=0;j<n;j++)
- a[i][j]=tmp[i][j];
- }
- LL init[N][N]={
- {2,0,0,0,0,0},
- {1,0,0,0,0,0},
- {27,0,0,0,0,0},
- {9,0,0,0,0,0},
- {3,0,0,0,0,0},
- {1,0,0,0,0,0}
- };
- LL a[N][N]={
- {1,2,1,0,0,0},
- {1,0,0,0,0,0},
- {0,0,1,3,3,1},
- {0,0,0,1,2,1},
- {0,0,0,0,1,1},
- {0,0,0,0,0,1}
- };
- LL b[N][N]={
- {1,2,1,0,0,0},
- {1,0,0,0,0,0},
- {0,0,1,3,3,1},
- {0,0,0,1,2,1},
- {0,0,0,0,1,1},
- {0,0,0,0,0,1}
- };
- LL res[N][N];
- void Pow(LL a[][N],LL n)
- {
- for(int i=0;i<N;i++)
- for(int j=0;j<N;j++) res[i][j]=init[i][j],a[i][j]=b[i][j];
- while(n)
- {
- if(n&1)
- multi(res,a,N);
- multi(a,a,N);
- n>>=1;
- }
- }
- int main(){
- int q;
- cin>>q;
- while(q--){
- LL n;
- cin>>n;
- Pow(a,n-2);
- cout<<res[0][0]<<endl;
- }
- system("pause");
- }
- View Code
- 2:26(2A)
来源: http://www.bubuko.com/infodetail-2990077.html