2023.08.15杭电多校第九场
solved：2
已完成：BEL
B.Shortest path
题意：给定一个数，可以通过除二（%2==0时），除三（%3==0时），减一三种操作变化，问最少多少次可以变成1；
暴搜+记忆化搜素；
开始觉得这样暴搜太暴力了总感觉会把取的log整回去，看了题解之后写了一发暴搜+记忆化搜索交vjudge居然过了，想了一下，可能重复的数比较多？，佬说记忆化搜素会跑的飞快，并给了一道题（指路：Problem - D - Codeforces）有空写；
1 #include<bits/stdc++.h> 2 #define ll long long 3 using namespace std; 4 ll read(){ 5 char ch=getchar();ll x=0,f=1; 6 while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();} 7 while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();} 8 return x*f; 9 } 10 ll T,N; 11 map<ll,ll> mapp; 12 ll work(ll x){ 13 if(x<=1)return 0; 14 if(mapp[x])return mapp[x]; 15 return mapp[x]=min(work(x/2)+x%2+1,work(x/3)+x%3+1); 16 } 17 int main(){ 18 T=read(); 19 while(T--){ 20 N=read(); 21 cout<<work(N)<<endl; 22 } 23 return 0; 24 }
E.List Reshape
题意：给定长度为N的序列，N=x*y，划分成长度为y的x个序列输出
模拟即可；
1 #include<bits/stdc++.h> 2 #define ll long long 3 using namespace std; 4 int read(){ 5 char ch=getchar();int x=0,f=1; 6 while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();} 7 while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();} 8 return x*f; 9 } 10 const int maxn=5e5+5; 11 ll T,x,y,tot; 12 string s; 13 ll A[maxn]; 14 void clear(){ 15 for(int i=1;i<=tot;i++)A[i]=0; 16 tot=0; 17 } 18 int main(){ 19 T=read(); 20 while(T--){ 21 tot=0; 22 while(1){ 23 char ch=getchar(); 24 bool flag=0; 25 while(ch<'0'||ch>'9'){ 26 if(ch=='\n'){ 27 flag=true;break; 28 } 29 ch=getchar(); 30 } 31 if(flag)break; 32 int res=0; 33 while(ch>='0'&&ch<='9'){ 34 res=res*10+ch-'0';ch=getchar(); 35 } 36 tot++;A[tot]=res; 37 } 38 39 x=read();y=read(); 40 cout<<"["; 41 for(int i=0;i<x;i++){ 42 cout<<"["; 43 for(int j=1;j<=y;j++){ 44 cout<<A[i*y+j]; 45 if(j!=y)cout<<", "; 46 } 47 cout<<"]"; 48 if(i!=x-1)cout<<", "; 49 } 50 cout<<"]"<<endl; 51 clear(); 52 } 53 return 0; 54 }
H.Coins
题意：N个人做游戏，第i个人手上有A[i]个硬币，每次游戏随机选取两个人，第一个给第二个一个硬币，若硬币没了则退场，若一个人拥有了在场的全部硬币则游戏结束；问游戏局数的期望值；
鞅的停时定理，不会；佬说做这题是手推几组样例推出来的；
写了个代码交vjudge一直t；
（更新：在把快读改成关闭流同步的cin之后成功AC）
1 #include<bits/stdc++.h> 2 #define ll long long 3 #define int128 __int128_t 4 using namespace std; 5 ll read(){ 6 char ch=getchar();ll x=0,f=1; 7 while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();} 8 while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();} 9 return x*f; 10 } 11 void write(int128 x){ 12 if(x<0){putchar('-'),x=-x;} 13 if(x>9)write(x/10); 14 putchar(x%10+'0'); 15 } 16 const int maxn=1e5+5; 17 ll A[maxn]; 18 19 int main(){ 20 ios::sync_with_stdio(false); 21 cin.tie(0),cout.tie(0); 22 ll T,N; 23 int128 s; 24 cin>>T; 25 while(T--){ 26 cin>>N; 27 s=0; 28 for(int i=1;i<=N;i++){ 29 cin>>A[i];A[i]+=A[i-1]; 30 } 31 for(int i=1;i<=N;i++){ 32 s+=(A[N]-A[i])*(A[i]-A[i-1]); 33 } 34 write(s); 35 } 36 return 0; 37 }
L.Inference
题意：对于M个数据，给定前M-1个，与N组数据，与一些数据间的影响关系，问第M个最可能的取值；
对于每组数据，如果影响第M个数据的数都与给定的相同，那么第M个数取当前这组数据的M的取值的可能性+1，最后选可能最大的即可；
1 #include<bits/stdc++.h> 2 #define ll long long 3 using namespace std; 4 ll read(){ 5 char ch=getchar();ll x=0,f=1; 6 while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();} 7 while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();} 8 return x*f; 9 } 10 const int maxn=1e4+5; 11 const int maxm=105; 12 ll T,N,M,K,x,y,cnt0,cnt1,cnt2; 13 ll A[maxm],t[maxn][maxm]; 14 vector<ll> v; 15 void pd(int x){ 16 bool flag=true; 17 for(int i=0;i<v.size();i++){ 18 if(t[x][v[i]]!=A[v[i]])flag=false; 19 } 20 if(flag){ 21 if(t[x][M]==0)cnt0++; 22 if(t[x][M]==1)cnt1++; 23 if(t[x][M]==2)cnt2++; 24 } 25 } 26 void clear(){ 27 v.clear(); 28 for(int i=1;i<=N;i++){ 29 for(int j=1;j<=M;j++){ 30 t[i][j]=0;A[j]=0; 31 } 32 } 33 } 34 int main(){ 35 T=read(); 36 while(T--){ 37 N=read();M=read();K=read(); 38 for(int i=1;i<=K;i++){ 39 x=read();y=read(); 40 if(y==M)v.push_back(x); 41 } 42 for(int i=1;i<=N;i++){ 43 for(int j=1;j<=M;j++){ 44 t[i][j]=read(); 45 } 46 } 47 for(int i=1;i<=M-1;i++){ 48 A[i]=read(); 49 } 50 cnt0=cnt1=cnt2=0; 51 for(int i=1;i<=N;i++){ 52 pd(i); 53 } 54 if(cnt0>cnt1&&cnt0>cnt2){ 55 cout<<"0"<<endl; 56 } 57 else if(cnt1>cnt2){ 58 cout<<"1"<<endl; 59 } 60 else{ 61 cout<<"2"<<endl; 62 } 63 clear(); 64 } 65 return 0; 66 }