A.?貝殼找房函數最值

常規貪心推式子。按(a-1)/b排序

#include <bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<=b;++i) #define frep(i,a,b) for(int i=a;i>=b;--i) #define mem(W) memset(W,0,sizeof(W)) #define pb push_back typedef long long ll; const int N = 1e5+100; const int inf = 0x3f3f3f3f; inline int read() {char c=getchar(); int x=0,f=1;while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}return x*f; } using namespace std; int n,x; struct node{int a,b;} A[N]; bool cmp(node x,node y) {return (x.a-1)*y.b > (y.a-1)*x.b; } int main() {int T = read();while(T--){n = read(); x= read();rep(i,1,n)A[i].a=read();rep(i,1,n)A[i].b=read();sort(A+1,A+1+n,cmp);frep(i,n,1) x = (A[i].a*x%10+ A[i].b)%10;printf("%d\n",x);}return 0; }

D.?貝殼找房魔法師顧問

情況1：兩邊都不可變。對比是否相等，直接判斷；

情況2：兩邊都變。對于每個聯通塊找一顆生成樹最優；

情況3：一邊可變，另一邊固定。對每個弱聯通分量，如果是DAG，顯然可以按拓撲序連成鏈即可保證連接關系，如果有環就把所有節點串成環，它們就可以完成任意的變化了。

#include <bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<=b;++i) #define frep(i,a,b) for(int i=a;i>=b;--i) #define mem(W) memset(W,0,sizeof(W)) #define pb push_back typedef long long ll; const int N = 2e5+100; const int inf = 0x3f3f3f3f; inline int read() {char c=getchar(); int x=0,f=1;while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}return x*f; } using namespace std; int n, a[N], b[N]; map<int,int> M[N],M2[N]; char s1[111],s2[111]; struct edge{int u,v,nxt;}E[N*2][2]; int cc,h[N][2]; void add(int u,int v) {++cc;E[cc][0].u=u;E[cc][0].v=v;E[cc][0].nxt=h[u][0];h[u][0]=cc;E[cc][1].u=v;E[cc][1].v=u;E[cc][1].nxt=h[v][1];h[v][1]=cc; } int vis[N];vector<int> s; int dfs1(int u){vis[u] = 1;s.pb(u);int ans = 1;for(int i=h[u][0];~i;i=E[i][0].nxt) {int v = E[i][0].v;if(!vis[v])ans += dfs1(v);}for(int i=h[u][1];~i;i=E[i][1].nxt) {int v = E[i][1].v;if(!vis[v]) ans += dfs1(v);}return ans; } int vis1[N]; int in[N],q[N],tp; int inc() {int n=s.size();tp = 0; rep(i,0,n-1) if(!in[s[i]]) q[tp++]=s[i];rep(i,0,tp-1) {for(int j=h[q[i]][0];~j;j=E[j][0].nxt) {--in[E[j][0].v];if(!in[E[j][0].v]) q[tp++]=E[j][0].v;}} // if(n==2){ // rep(i,0,n-1)cout << s[i] << endl; // }s.clear(); // if(n==2){ // cout << tp << endl; // }return (n != tp); } int solve() {int ans = 0;rep(i,1,100000)if(!vis[i]){ans += (dfs1(i) - !(inc()));}return ans; }int bfs(int s) {int ans = 0;vis[s]=1;++ans;queue<int> q;q.push(s);while(!q.empty()){int u=q.front();q.pop();for(int i=h[u][0];~i;i=E[i][0].nxt){int v = E[i][0].v;if(!vis[v]){vis[v]=1;++ans;q.push(v);}}}return ans; }int main() {n = read();//int m=read();memset(h,-1,sizeof(h)); // rep(i,1,m){int u,v; // scanf("%d%d",&u,&v); // add(u,v); // ++in[v]; // } // rep(i,1,n)s.pb(i); // inc();scanf(" %s",s1);rep(i,1,n)scanf("%d",&a[i]);scanf(" %s",s2);rep(i,1,n)scanf("%d",&b[i]);if(s1[0]=='C'&&s2[0]=='C'){int f=0;rep(i,1,n)if(a[i]!=b[i]){f=1;break;}if(f)puts("-1");else puts("0");}else {if(s1[0]=='C'&&s2[0]!='C'){int ans=0;rep(i,1,n)if(a[i]!=b[i]&&!M[b[i]][a[i]]){add(b[i],a[i]); ++in[a[i]];M[b[i]][a[i]]=1;}printf("%d\n",solve());}else if(s1[0]!='C'&&s2[0]=='C'){int ans=0;rep(i,1,n)if(a[i]!=b[i]&&!M[a[i]][b[i]]){add(a[i],b[i]); ++in[b[i]];M[a[i]][b[i]] = 1;}printf("%d\n",solve());}else {rep(i,1,n)if(a[i]!=b[i]&&!M[a[i]][b[i]]){add(a[i],b[i]);add(b[i],a[i]);M[a[i]][b[i]] = M[b[i]][a[i]] = 1;}int ans=0;rep(i,1,100000)if(!vis[i])ans+=bfs(i)-1;printf("%d\n",ans);}}return 0; }

G.?貝殼找房計數比賽

字符串的排列數 = (長度)!/(a的數目!)/.../(z的數目!)，先把t挑出來。剩下的放到兩邊，就相當于把剩余字符的全排列，從一個位置分成兩塊，有(n+1)個位置。

#include <bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<=b;++i) #define frep(i,a,b) for(int i=a;i>=b;--i) #define mem(W) memset(W,0,sizeof(W)) typedef long long ll; const int N = 1e5+100; const int inf = 0x3f3f3f3f; const ll mod = 1e9 + 7; inline int read() {char c=getchar(); int x=0,f=1;while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}return x*f; } using namespace std; int n,a[N],A[27]; string s1,s2; int p[N], notp[N], nxt[N], b[N]; void init(){notp[1]=1;nxt[1]=1;for(int i=2;i<=100000;++i) {if(!notp[i]) p[++p[0]]=i,nxt[i]=i;for(int j=1;j<=p[0]&&i*p[j]<=100000;++j) {notp[i*p[j]] = 1;nxt[i*p[j]]=p[j];if(i%p[j]==0)break;}} } ll q_pow(ll a,ll b) {ll ans=1;while(b) {if(b&1LL) ans=(ans*a)%mod;a=(a*a)%mod;b>>=1LL;}return ans; } inline void add(int x,int f) {while(x!=1){b[nxt[x]]+=f;x/=nxt[x];} } ll cal() {ll ans = 1;rep(i,1,p[0])ans = (ans*q_pow(p[i],b[p[i]]))%mod;return ans%mod; } int main() {init();int T = read();while(T--) {int f=0, num=0;cin >> s1 >> s2;mem(A);mem(b);int n1=s1.size(), n2=s2.size();rep(i,0,n1-1) ++A[s1[i]-'a'];rep(i,0,n2-1) --A[s2[i]-'a'];rep(i,0,25){if(A[i]<0){puts("0");f=1;break;}num += A[i];}if(f)continue;rep(i,1,num) add(i,1);rep(i,0,25) rep(j,1,A[i]) add(j,-1);printf("%lld\n", (cal()*(num+1))%mod);}return 0; }

　　

轉載于:https://www.cnblogs.com/RRRR-wys/p/9201752.html

總結

以上是生活随笔為你收集整理的2018 计蒜之道 复赛的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。