2019河北省大学生程序设计竞赛（重现赛）

记得补题！

https://ac.nowcoder.com/acm/contest/903#question

B：

大佬跟我说可以直接矩阵快速幂加速。。。怎末做呢？构建一个2*2的矩阵t第一行是1 0，第二行是q q。然后就是套矩阵快速幂就可以了。递推公式是Si=Si-1+(ai-1)*q。在取模的情况下，有一个确定的递推公式，让你求第n个数，一般都是矩阵快速幂。至于求逆元咋搞，我还没想明白，之后看看再说吧。

#include<bits/stdc++.h> using namespace std; #define ll long long ll q,n,mod; struct s{ ll g[3][3]; }; s mul(s a,s b){ s tp; memset(tp.g,0,sizeof(tp.g)); for(int i=1;i<=2;i++){ for(int j=1;j<=2;j++){ for(int k=1;k<=2;k++){ tp.g[i][j]+=a.g[i][k]*b.g[k][j]; tp.g[i][j]%=mod; } } } return tp; } s mpow(s ans,int n){ s tp; tp.g[1][1]=1;tp.g[1][2]=0; tp.g[2][1]=tp.g[2][2]=q; while(n){ if(n&1) ans=mul(ans,tp); tp=mul(tp,tp); n>>=1; } return ans; } int main() { int t; scanf("%d",&t); while(t--){ scanf("%lld%lld%lld",&q,&n,&mod); if(1==q){ printf("%lld\n",n%mod); }else{ s ans; ans.g[1][1]=ans.g[2][2]=1; ans.g[1][2]=ans.g[2][1]=0; ans=mpow(ans,n); printf("%lld\n",ans.g[2][1]%mod); } } return 0; }

 C:

啥分治啊。。。咋感觉区间dp更容易看出来。。。

#include <bits/stdc++.h> using namespace std; #define ll long long #define inf 0x3f3f3f3f const int maxn=105; int dp[maxn][maxn],cost[maxn]; int main() { int t,n; scanf("%d",&t); while(t--){ memset(dp,0,sizeof(dp)); scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&cost[i]); for(int t=2;t<=n;t++){ for(int l=1;l<=n-t+1;l++){ int r=l+t-1; for(int i=l;i<=r;i++){ if(!dp[l][r]) dp[l][r]=dp[l][i-1]+dp[i+1][r]+(t-1)*cost[i]; else dp[l][r]=min(dp[l][r],dp[l][i-1]+dp[i+1][r]+(t-1)*cost[i]); } } } printf("%d\n",dp[1][n]); } return 0; }

G：签到

#include <bits/stdc++.h> using namespace std; int main() { int n; scanf("%d",&n); if(0==n%2&&n) printf("qiandaochenggong"); else printf("qiandaoshibai"); return 0; }

H：签到

#include <bits/stdc++.h> using namespace std; #define ll long long #define inf 0x3f3f3f3f ll f(ll x){ ll tp=0; while(x){ tp+=x; x/=10; } return tp; } int main() { int t; ll n,k; scanf("%d",&t); while(t--){ scanf("%lld%lld",&n,&k); if(2==k) n*=n; while(n>=10){ n=f(n); } printf("%lld\n",n); } return 0; }

 J：舔狗

贪心的做法，记录入度，每次都先择入度最小的舔狗i，和他喜欢的人j匹配。因为j也有喜欢的人k。所以i和j匹配了之后，k的入度要-1。优先队列维护就行。

#include<bits/stdc++.h> using namespace std; #define ll long long const int maxn=1e6+5; int like[maxn],in[maxn],n,vis[maxn]; struct Node{ int id,cnt; bool operator<(const Node a)const{ return this->cnt>a.cnt; } }; priority_queue<Node> q; int slove(){ while(!q.empty()){ Node t=q.top(); int tp=t.id; q.pop(); if(vis[tp]||vis[like[tp]]) continue; in[like[tp]]--; vis[tp]=vis[like[tp]]=1; tp=like[like[tp]]; in[tp]--; q.push((Node){tp,in[tp]}); } int ans=0; for(int i=1;i<=n;i++){ if(!vis[i]) ans++; } return ans; } int main() { scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&like[i]); in[like[i]]++; } for(int i=1;i<n;i++){ q.push((Node){i,in[i]}); } printf("%d",slove()); return 0; }

 K:河北美食

#include <bits/stdc++.h> using namespace std; #define ll long long #define inf 0x3f3f3f3f map<string,int> Map; vector<string> v; int main() { int n,m,t,q; string s; scanf("%d%d",&n,&m); for(int i=0;i<n;i++){ cin>>s>>t, Map[s]=t; v.push_back(s); } int flag=true; for(int i=0;i<m;i++){ cin>>q; while(q--){ cin>>s>>t; if(flag&&Map[s]>=t){ Map[s]-=t; }else{ flag=false; } } } if(flag){ printf("YES\n"); t=v.size(); for(int i=0;i<t;i++){ if(0!=Map[v[i]]) cout<<v[i]<<" "<<Map[v[i]]<<endl; } }else{ printf("NO\n"); } return 0; }

 L：smart robot

只在原地的数都是一位数，两位数咋走？就是当前格子*10+周围格子走一步的情况的值。走4步怎样走？就是当前格子*1000+周围格子走3步。用set解决，走第i步我们要知道第i-1步的状态，用滚动数组优化。每获得一个值就vis标记，最后看最小的没有被标记的数就是结果。

#include <bits/stdc++.h> using namespace std; #define ll long long #define inf 0x3f3f3f3f const int maxn=55; int G[maxn][maxn],n; set<int> GG[2][maxn][maxn]; int vis[1000000],to[4][2]={{1,0},{-1,0},{0,1},{0,-1}}; bool isin(int x,int y){ if(x<1||y<1||x>n||y>n) return false; else return true; } int main(){ scanf("%d",&n); for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){ scanf("%d",&G[i][j]); GG[0][i][j].insert(G[i][j]); vis[G[i][j]]=1; } int pos1=1,pos2=0; int tp=10; for(int w=2;w<=6&&w<=n;w++){ for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ for(int k=0;k<4;k++){ int nx=i+to[k][0],ny=j+to[k][1]; if(isin(nx,ny)){ set<int>::iterator it; for(it=GG[pos2][nx][ny].begin();it!=GG[pos2][nx][ny].end();it++){ int m=G[i][j]*tp+*it; vis[m]=1; GG[pos1][i][j].insert(m); } } } } } tp*=10; pos1=pos1==1?0:1; pos2=pos2==1?0:1; } for(int i=0;i<1000000;i++){ if(!vis[i]){ printf("%d",i); return 0; } } return 0; }