E2. Rotate Columns (hard version)
题意：有一个n行m列的矩阵 每一列可以任意旋转平移 问经过操作后每一行的最大值能为多少
注意到n非常小 m很大
首先可以优化m 显然只要考虑最大值最大的n列即可
所以就转化为了一个n行n列的矩阵
可以考虑状压dp
注意要维护三个数组
#include<bits/stdc++.h> using namespace std; #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i>=(b);--i) #define ll long long #define see(x) (cerr<<(#x)<<'='<<(x)<<endl) #define inf 0x3f3f3f3f #define CLR(A,v) memset(A,v,sizeof A) ///////////////////////////////////// const int N=1e5+10; int n,m,a[20][2000+10],id[N],maxx[N],dp[1<<13],olddp[1<<13],temp[1<<13]; int main() { int cas;cin>>cas; while(cas--) { memset(dp,0,sizeof dp); memset(olddp,0,sizeof olddp); memset(maxx,0,sizeof maxx); scanf("%d%d",&n,&m); rep(i,0,n-1)rep(j,1,m) scanf("%d",&a[i][j]),maxx[j]=max(maxx[j],a[i][j]); rep(i,1,m)id[i]=i; sort(id+1,id+1+m,[](int x,int y){return maxx[x]>maxx[y];}); m=min(m,n); //rep(i,1,m)printf("%lld ",maxx[id[i]]);cout<<endl; rep(i,1,m) { memcpy(olddp,dp,sizeof dp); memset(temp,0,sizeof temp); for(int state=0;state<(1<<n);++state){ for(int k=0;k<n;k++) { int sum=0; for(int now=0;now<n;++now) if( 1&(state>>now))sum+=a[(now+k)%n][id[i]]; temp[state]=max(temp[state],sum); } for(int state2=state;state2<(1<<n); state2= ((state2+1)|state) ) dp[state2]=max(dp[state2],temp[state]+olddp[state2^state]); } } printf("%d ",dp[(1<<n)-1]); } return 0; }
F. Koala and Notebook
题意：有n个点 m条有向边 边权为边的编号
输出1到 2-n的“最短路” （最短路为经过边的边权组合而成的最小数）
显然要贪心得遍历 但是其结果和长度有关 长度越小数字肯定小 然后比字典序
一些边的编号长一些边的编号短 所以首先一定要进行预处理
建立虚点 每条边的权值小于10 所以控制了长度 那么就可以进行bfs 了 第一个到的肯定是长度最小的
并且要进行贪心的bfs
注意vector的使用！！！
一开始没用vector 那么 234 256的情况没法 如果先跑了256了答案就会出错
设置成一组一组即可避免错误
#include<bits/stdc++.h> using namespace std; #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i>=(b);--i) #define ll long long #define see(x) (cerr<<(#x)<<'='<<(x)<<endl) #define inf 0x3f3f3f3f #define CLR(A,v) memset(A,v,sizeof A) ////////////////////////////////// const int N= 2e6+5 ; const ll mod=1e9+7; vector<int>edge[N][11]; int n,m,pos,vis[N],v; ll ans[N]; inline void add(int a,int b,int c) { for(;c>9;c/=10)edge[++pos][c%10].push_back(b),b=pos; edge[a][c].push_back(b); } inline void bfs() { queue< vector<int> >q; vector<int>u; u.push_back(1); vis[1]=1;q.push(u); while(!q.empty()) { u=q.front(); q.pop(); rep(i,0,9) { vector<int> temp; for(auto v:u) for(auto w:edge[v][i])if(!vis[w]) vis[w]=1,ans[w]=(ans[v]*10+i)%mod,temp.push_back(w); if(temp.size())q.push(temp); } } } int main() { cin>>n>>m;pos=n;int u,v; rep(i,1,m)scanf("%d%d",&u,&v),add(u,v,i),add(v,u,i); bfs(); rep(i,2,n)printf("%lld ",ans[i]); return 0; }
G1. Into Blocks (easy version)
题意： 给定一个数字序列a 将一个数字（所有）变为另一个数字的代价为这个数字的个数
问构成good序列的最小代价
good序列 如果序列中两个数相同那么他们之间的数字和他们相同
代码很好懂 妙呀
#include<bits/stdc++.h> using namespace std; #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i>=(b);--i) #define ll long long #define see(x) (cerr<<(#x)<<'='<<(x)<<endl) #define inf 0x3f3f3f3f #define CLR(A,v) memset(A,v,sizeof A) ////////////////////////////////// const int N=2e6+10; int last[N],cnt[N],a[N],num,ans; int main() { int n,q,l,r; cin>>n>>q; rep(i,1,n) scanf("%d",&a[i]),last[a[i]]=i,cnt[a[i]]++; rep(i,1,n) { l=i;r=last[a[i]];num=cnt[a[i]]; while(i<r)i++,r=max(r,last[a[i]]),num=max(num,cnt[a[i]]); ans+=r-l+1-num; } cout<<ans; return 0; }