A.数数
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e5+5; const ll mod=1e9+7; int main(){ int t; cin>>t; while(t--){ int n; cin>>n; int x=n%10; int s=10; int sum=0; for(int i=1;i<x;i++)sum+=10; if(n/10==0)sum+=1; else if(n/100==0)sum+=3; else if(n/1000==0)sum+=6; else sum+=10; cout<<sum<<endl; } return 0; }
B.1之间0的个数
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e5+5; const ll mod=1e9+7; int minn=100000; int n; int a[N]; int main(){ int t; cin>>t; while(t--){ scanf("%d",&n); int sum=0; int l=-1; for(int i=1;i<=n;i++){ scanf("%d",&a[i]); if(a[i]==1) if(l==-1)l=i; else sum+=i-l-1,l=i; } cout<<sum<<endl; } return 0; }
C.找出最大值并且两边至少有一个小于它的点，这样他就可以进化了成为新的最大。
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=4e5+5; const ll mod=1e9+7; int minn=100000; int n; int a[N]; int main(){ int t; cin>>t; while(t--){ int n;scanf("%d",&n); int f=0; int z=0; int maxn=-1; for(int i=1;i<=n;i++){ scanf("%d",&a[i]); if(a[i]>maxn)maxn=a[i]; if(i!=1&&a[i]!=a[i-1])f=1; } for(int i=1;i<=n;i++){ if(z)break; if(a[i]==maxn){ if(i-1>=1&&a[i-1]!=maxn) z=i; if(i+1<=n&&a[i+1]!=maxn) z=i; } } if(!f)cout<<-1<<endl; else cout<<z<<endl; } return 0; }
D.构造一个图，首先我们选不同的两个点相连，这样再将其余的点连到这两个点之一上。
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=4e5+5; const ll mod=1e9+7; int minn=100000; int n; int a[N]; int main(){ int t; cin>>t; while(t--){ int n;scanf("%d",&n); int f=0; int l,r; for(int i=1;i<=n;i++){ scanf("%d",&a[i]); if(i!=1&&a[i]!=a[i-1]){ l=i-1; r=i; f=1; } } if(!f)printf("NO "); else{ printf("YES "); printf("%d %d ",l,r); for(int i=1;i<=n;i++){ if(i==l||i==r)continue; if(a[i]!=a[l]){ printf("%d %d ",i,l); }else{ printf("%d %d ",i,r); } } } } return 0; }
E.n个人，分人数相同的两组成环的方案数。
1：n人成环的方案数为 (n-1)！
因此先分两份且不重复，C(N,N/2)/2
再乘以两边的环排列
最终为C(N,N/2)/2*(N/2-1)!*(N/2-1)!
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=4e5+5; const ll mod=1e9+7; int minn=100000; int n; ll a[N]; void init(){ a[0]=1; for(int i=1;i<=20;i++)a[i]=a[i-1]*i; } ll c(ll m){ return a[m]/a[(m/2)]/a[(m/2)]; } int main(){ init(); int t; ll n; cin>>n; if(n==2){ cout<<1<<endl; return 0; }else{ ll l=n/2; ll sum=1; sum*=c(n)/2; sum*=a[(n/2)-1]; sum*=a[(n/2)-1]; cout<<sum<<endl; } return 0; }
F.DP bitset 优化，但是有更好的方法，我写的烂，别学
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=300000; const ll mod=1e9+7; bitset<N> st; int g[N]; int a[100][100]; int main(){ int n,m,k; scanf("%d%d%d",&n,&m,&k); int i,j; int maxn=0; st[0]=1; for(i=1;i<=n;i++){ for(j=1;j<=m;j++){ scanf("%d",&a[i][j]); for(int k=maxn+a[i][j];k>=a[i][j];k--){ int op=k-a[i][j]; if(st[k]){ if(st[op]) g[k]=min(g[op]+1,g[k]); }else{ if(st[op]){ if(g[op]<m/2){ g[k]=g[op]+1; st[k]=1; maxn=max(maxn,k); } } } } } memset(g,0,sizeof g); } for(i=(maxn+160)/k*k;i>=0;i-=k){ if(st[i]){ printf("%d ",i); return 0; } } return 0; }
G.让一条边为0，给的点对的最短路的总和最小
先算出所有点对的最短路
枚举每一条边，为0，在判断大小
1:经过该点
2:不过
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll,ll> p; const int N=1001; const int M=100005; int n,m,k; int head[N]; ll s[N][N]; ll dis[N]; int vis[N]; struct edge{ int from,to,ne,dis; }e[M]; int cnt; void add(int x,int y,int w){ e[cnt].from=x,e[cnt].to=y,e[cnt].dis=w,e[cnt].ne=head[x],head[x]=cnt++; } void dij(int b){ int begin=b; memset(dis,0x3f,sizeof dis); memset(vis,0,sizeof vis); dis[b]=0; priority_queue<p,vector<p> ,greater<p> >st; st.push({0,begin}); while(!st.empty()){ p x=st.top(); st.pop(); int v=x.second; if(vis[v])continue; vis[v]=1; for(int i=head[v];~i;i=e[i].ne){ int j=e[i].to,w=e[i].dis; if(dis[j]>dis[v]+w){ dis[j]=dis[v]+w; st.push({dis[j],j}); } } } for(int i=1;i<=n;i++)s[b][i]=dis[i]; } vector<p> sk; int main(){ memset(head,-1,sizeof head); scanf("%d%d%d",&n,&m,&k); for(int i=1;i<=m;i++){ int x,y,w;scanf("%d%d%d",&x,&y,&w); add(x,y,w);add(y,x,w); } for(int i=1;i<=k;i++){ ll x,y;scanf("%lld%lld",&x,&y); sk.push_back({x,y}); } ll minn=1e18; for(int i=1;i<=n;i++)dij(i); for(int i=0;i<2*m;i+=2){ ll sum=0; int x=e[i].from,y=e[i].to; for(int j=0;j<k;j++){ int f=sk[j].first,tt=sk[j].second; sum+=min(s[f][tt],min(s[f][x]+s[y][tt],s[f][y]+s[x][tt])); } minn=min(minn,sum); } cout<<minn<<endl; }