暑假第七测
发布时间：2020-12-14 03:20:17 所属栏目：大数据 来源：网络整理
导读：i ? ? ? 题解：第一题：状压+贪心； 我们发现两个质数对同时选对结果的影响就是他们的LCM，所以30以上的质数不会互相影响的；而30以下的质数只有10个，30以上也就40多个，所以30以下状压，枚举所有状态，30以上贪心，看他加进来的贡献0就选；(2^10 * 30） #i
|
i
? ?
? 题解：第一题：状压+贪心； 我们发现两个质数对同时选对结果的影响就是他们的LCM，所以30以上的质数不会互相影响的；而30以下的质数只有10个，30以上也就40多个，所以30以下状压，枚举所有状态，30以上贪心，看他加进来的贡献>0就选；(2^10 * 30）
#include<bits/stdc++.h> using namespace std; const int N = 1005; bool f[N]; int a[N]; int main(){ freopen("a.in","r",stdin); freopen("a.out","w",stdout); int T; scanf("%d",&T); while(T--){ int n,m,ans = 0; scanf("%d%d",&n,&m); for(int i = 1; i <= m; i++)scanf("%d",&a[i]); sort(a+1,a+1+m); int q = unique(a+1,a+1+m) - a - 1,st; for( q; a[q] > n; q--); for(st = 1; a[st] <= 31 && st <= q; st++); if(st > q)st = q; for(int i = 1; i < (1<<(st)); i++){ memset(f,0,sizeof(f)); int j,cnt = 0; for(j = 1; j <= st; j++) if(i & (1 << (j-1))) for(int k = a[j]; k <= n; k += a[j]) f[k] ^= 1; for( ; j <= q; j++) { int c = 0; for(int k = a[j]; k <= n; k += a[j]) f[k] ? c-- : c++; if(c > 0) for(int k = a[j]; k <= n; k += a[j]) f[k] ^= 1; } for(int k = 1; k <= n; k++)if(f[k]) cnt++; ans = max(cnt,ans);// cout<<cnt<<" "<<i<<endl; } printf("%dn",ans); } } ? 第二题：数据这么大又要拆位，而前面一样的贡献有一样，所以是一个裸地Trie树（太妙了），一位一位找，O(18*10*n)
#include<bits/stdc++.h> using namespace std; const int N = 1e7 + 20; int num[21],tot; #define ll long long int struct Trie{ int ch[N][10]; void insert(){ int u = 0; for(int i = 1; i <= 20; i++){ if(ch[u][num[i]])u = ch[u][num[i]]; else ch[u][num[i]] = ++tot,u = tot; } } ll query(){ int u = 0; ll x = 0; for(int i = 1; i <= 20; i++){ int tmp = -1,ret = -1; for(int j = 0; j <= 9; j++) if(ch[u][j]){ //printf("%d %dn",i,j); int t = (j + num[i]) % 10; if(t > tmp) tmp = t,ret = ch[u][j]; if(tmp == 9)break; } x = x*10 + tmp,u = ret; } return x; } ll query2(){ int u = 0; ll x = 0; for(int i = 1; i <= 20; i++){ int tmp = 11,ret = -1; for(int j = 0; j <= 9; j++) if(ch[u][j]){ int t = (j + num[i]) % 10; if(t < tmp) tmp = t,ret = ch[u][j]; if(!tmp)break; } x = x*10 + tmp,u = ret; } return x; } }Tr; int main(){ freopen("b.in",stdin); freopen("b.out",stdout); int n; ll a1 = 0,a2 = 9e18; scanf("%d",&n); ll u; scanf("%I64d",&u); for(int j = 1; u; j++)num[j] = u%10,u /= 10; for(int j = 1; j <= 10; j++)swap(num[j],num[21-j]); Tr.insert(); for(int i = 2; i <= n; i++){ ll u; scanf("%I64d",&u); memset(num,sizeof(num)); for(int j = 1; u; j++)num[j] = u%10,u /= 10; for(int j = 1; j <= 10; j++) swap(num[j],num[21-j]); a1 = max(a1,Tr.query()); a2 = min(a2,Tr.query2()); Tr.insert(); //printf("%d %I64d %I64dn",a1,a2); } printf("%I64d %I64dn",a2,a1); } ? 第三题：网络流，一道原题，我还是错了，要证明一条边在最短路上的唯一方法是 dis[st--u] + G[i].w = dis[v--ed];
#include<bits/stdc++.h> using namespace std; const int inf = 1e9,N = 10005,M = 200005; void read(int &x){ x=0;int f=1;char c=getchar(); while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();} x*=f; } int tot,tot2,st,ed,n,h[N],hh[N];//,pre[N],pree[M]; struct edge{int v,nxt,f;}G[M],g[M]; struct Netflow{ int ret,dis[N],diss[N]; bool inq[N]; void init(){ tot2 = tot = 1; memset(h,0,sizeof(h)); memset(hh,sizeof(hh)); } void add(int u,int v,int f,int s){ if(s == 1){G[++tot].v = v; G[tot].f = f; G[tot].nxt = h[u]; h[u] = tot;} else {g[++tot2].v = v; g[tot2].f = f; g[tot2].nxt = hh[u]; hh[u] = tot2;} } void readd(int u,int v){ g[++tot2].v = v; g[tot2].f = 1; g[tot2].nxt = hh[u]; hh[u] = tot2; g[++tot2].v = u; g[tot2].f = 0; g[tot2].nxt = hh[v]; hh[v] = tot2; } void rebuild(){ memset(hh,sizeof(hh)); tot2 = 1; for(int u = 1; u <= n; u++) for(int i = h[u]; i; i = G[i].nxt){ int v = G[i].v; if(dis[v] + diss[u] + G[i].f == ret) readd(u,v); } } bool SPFA(){ queue <int> Q; memset(inq,sizeof(inq)); memset(dis,127/3,sizeof(dis)); dis[ed] = 0; inq[ed] = 1; Q.push(ed); while(!Q.empty()){ int u = Q.front(); Q.pop(); inq[u] = 0; for(int i = hh[u]; i; i = g[i].nxt){ int v = g[i].v; if(dis[v] > dis[u] + g[i].f){ dis[v] = dis[u] + g[i].f; if(!inq[v]){ Q.push(v); inq[v] = 1; } } } } return dis[st]; } bool SPFA2(){ queue <int> Q; memset(inq,sizeof(inq)); memset(diss,sizeof(diss)); diss[st] = 0; inq[st] = 1; Q.push(st); while(!Q.empty()){ int u = Q.front(); Q.pop(); inq[u] = 0; for(int i = h[u]; i; i = G[i].nxt){ int v = G[i].v; if(diss[v] > diss[u] + G[i].f){ diss[v] = diss[u] + G[i].f; if(!inq[v]){ Q.push(v); inq[v] = 1; } } } } } bool bfs(){ queue <int> Q; memset(inq,-1,sizeof(dis)); dis[st] = 0; inq[st] = 1; Q.push(st); while(!Q.empty()){ int u = Q.front(); Q.pop(); for(int i = hh[u]; i; i = g[i].nxt){ int v = g[i].v; if(g[i].f && !inq[v]){ dis[v] = dis[u] + 1; Q.push(v); inq[v] = 1; } } } return dis[ed] != -1; } int dfs(int u,int q){ if(u == ed || !q)return q; int ans = 0; for(int i = hh[u]; i; i = g[i].nxt){ int v = g[i].v; if(dis[v] != dis[u]+1)continue; int tt = dfs(v,min(q,g[i].f)); g[i].f -= tt; g[i^1].f += tt; ans += tt; q -= tt; } return ans; } int au(){ int ans = 0; if(!SPFA()) return ans; ret = dis[st]; SPFA2(); rebuild(); while(bfs()){ ans += dfs(st,inf); } return ans; } }Tr; int main(){ freopen("c.in",stdin); freopen("c.out",stdout); int T; scanf("%d",&T); while(T--){ int m; read(n),read(m); Tr.init(); for(int i = 1; i <= m; i++){ int u,v,w; read(u),read(v),read(w); Tr.add(u,w,1); Tr.add(v,u,2); } read(st),read(ed); printf("%dn",Tr.au()); } } ? 今天是科大的唐大爷来给我们讲课， 本来是郭大侠的， 不过唐大爷讲的挺好的，突然挺想科大的 （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
