好久不更博客之想水一篇博文之每个题只有几句话之
A. 10000以内，如果一个数的全部数位相同，那称为一个特殊的数。给你一个数，你需要输出在它之前(包括它)，所有特殊数的数位之和。
题解：前面的数，每四个数位和为10个。算一下就好了。
#include<bits/stdc++.h>
using namespace std;
int main(){
int _;cin>>_;
while(_--){
int x;cin>>x;
int sz=0, dig;
while(x){
++sz;
dig=x%10;
x/=10;
}
cout<<10*(dig-1)+sz*(sz+1)/2<<endl;
}
return 0;
}
B. 给你一个01串，你可以移动一些连续的1串，问将它们全部搞到一起(连续)所需要的最小步数。
题解：找出最左边和最右边的1，减去中间1的个数。
#include<bits/stdc++.h>
using namespace std;
const int N = 55;
int n;
int s[N];
int main(){
int _;cin>>_;
while(_--){
cin>>n;
for(int i=1;i<=n;++i){
cin>>s[i];
}
int st=-1, ed=-1, cnt=0;
for(int i=1;i<=n;++i){
if(s[i]==1){
if(st==-1)st=i;
ed=i;
++cnt;
}
}
cout<<ed-st+1-cnt<<endl;
}
return 0;
}
C. 给你一个数组，定义一个dominant的数，当且仅当如果一个数左边有数，且比左边的数大，则可以吃掉左边的这个数，右边的同理，吃掉一个数，自己会增加1，它能采取某种策略吃掉所有数。找出这样的数的下标，或者判断无解。
题解：显然要找最大的，如果一个最大的旁边的有比自己小的数，则可行。否则所有数相等，无解。
#include <bits/stdc++.h>
using namespace std;
const int N = 300005;
int a[N];
int main(){
int _;cin>>_;
while(_--){
int n;cin>>n;
for(int i=1;i<=n;++i){
cin>>a[i];
}
int mx=*max_element(a+1,a+n+1);
vector<int>v;
for(int i=1;i<=n;++i){
if(a[i]==mx){
v.push_back(i);
}
}
int res=-1;
for(auto& x:v){
if(x>1&&a[x]>a[x-1]){
res=x;
break;
}
if(x<n&&a[x]>a[x+1]){
res=x;
break;
}
}
cout<<res<<endl;
}
return 0;
}
D. 给你一些点，每个点有一个颜色。求一种构造方案，使得相同的不直接相连。
题解：如果只有一种颜色，那直接gg。否则，第一种颜色的第一个当中心。其他颜色的挂在这上面。如果有没用完的第一个颜色的点。挂在任意一种颜色的点后面。
#include <bits/stdc++.h>
using namespace std;
const int N = 5005;
vector<int> G[N];
int n, a[N];
int st[N], top;
int main(){
int _;cin>>_;
while(_--){
cin>>n;
top=0;
for(int i=1;i<=n;++i){
cin>>a[i];
st[++top]=a[i];
G[i].clear();
}
sort(st+1,st+top+1);
top=unique(st+1,st+top+1)-st-1;
for(int i=1;i<=n;++i){
a[i]=lower_bound(st+1,st+1+top,a[i])-st;
}
for(int i=1;i<=n;++i){
G[a[i]].push_back(i);
}
if((int)G[1].size()==n){
cout<<"NO"<<endl;
}else{
cout<<"YES"<<endl;
int nd=-1;
for(int i=2;i<=top;++i){
for(auto& v:G[i]){
cout<<G[1][0]<<" "<<v<<endl;
nd=v;
}
}
for(int i=1;i<(int)G[1].size();++i){
cout<<nd<<" "<<G[1][i]<<endl;
}
}
}
return 0;
}
E. 给你n个人，你要安排两个圆桌舞会，每一个舞会n/2个人。对于其中的每一个舞会，如果其圆排列相同，那被认为是一种方案，问总方案数。
题解：首先是从n个人中选出n/2个人，直接组合数。考虑到去重，我们除2。然后，由于圆排列是一种方案，我们干脆找到某一个数，让它作为头，后面随便排。这样肯定是不同的一种圆排列。
#include <bits/stdc++.h>
using namespace std;
const int N = 25;
typedef long long LL;
LL a[N];
int main(){
int n;cin>>n;
a[0]=1;
for(int i=1;i<=20;++i)a[i]=a[i-1]*i;
LL ans=a[n]/a[n/2]/a[n/2];
ans*=a[n/2-1];
ans*=a[n/2-1];
ans/=2;
cout<<ans;
return 0;
}
F. 给你n行m列的数表，每一行最多选k/2个数。求让k整除的最大和。
题解：每一行互不影响，用背包做出余数为j的最大和(人数不超过m/2，这里要加一维)。对于每一行分别dp。
#include <bits/stdc++.h>
using namespace std;
const int N = 75;
const int INF = 0x3f3f3f3f;
int dp[N][N];
int a[N][N];
int n, m, k;
int knap[2][N][N], mx[N];
void chmax(int& x, int y){
if(y>x)x=y;
}
int main(){
cin>>n>>m>>k;
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
cin>>a[i][j];
}
}
for(int i=0;i<=70;++i){
for(int j=0;j<=70;++j){
dp[i][j]=-INF;
}
}
dp[0][0]=0;
for(int i=1;i<=n;++i){
for(int j=0;j<k;++j){
for(int kk=0;kk<=m/2;++kk){
knap[0][kk][j]=knap[1][kk][j]=-INF;
}
}
knap[0][0][0]=0;
for(int j=1;j<=m;++j){
for(int kk=0;kk<k;++kk){
for(int l=0;l<=m/2;++l){
chmax(knap[j&1][l][kk],knap[(j&1)^1][l][kk]);
if(l+1<=m/2)chmax(knap[j&1][l+1][(kk+a[i][j])%k],knap[(j&1)^1][l][kk]+a[i][j]);
}
}
}
for(int j=0;j<k;++j)mx[j]=-INF;
for(int j=0;j<k;++j){
for(int kk=0;kk<=m/2;++kk){
chmax(mx[j],knap[m&1][kk][j]);
}
}
for(int j=0;j<k;++j){
for(int kk=0;kk<k;++kk){
chmax(dp[i][(j+kk)%k],dp[i-1][j]+mx[kk]);
}
}
}
cout<<dp[n][0];
return 0;
}
G. 无向联通图，有边权，给定k个起始点，现在可以将一条边边权改为0，求这k条边的最短路之和。
题解：首先，我们跑n次dijstra，处理出每个点的最短路数组。然后枚举一条边，如果在某一条路径的最短路树上，可以考虑拿它更新答案。
#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
#define fi first
#define se second
#define MP make_pair
#define PB push_back
typedef pair<int,int> PII;
vector<PII> G[N];
vector<vector<int>> E;
const int INF = 0x3f3f3f3f;
int route[N][2];
int n, m, num;
int dist[N][N], vis[N];
void chmin(int& x, int y){
if(y<x)x=y;
}
void dij(int s){
memset(vis,0,sizeof vis);
priority_queue<PII,vector<PII>,greater<PII> > q;
q.push({0,s});
while(!q.empty()){
int d, v;
PII p=q.top();
d=p.fi, v=p.se;
q.pop();
if(vis[v])continue;
vis[v]=1;
dist[s][v]=d;
for(auto& it:G[v]){
q.push({d+it.se,it.fi});
}
}
}
int main(){
cin>>n>>m>>num;
for(int i=1;i<=m;++i){
int u,v,w;
cin>>u>>v>>w;
G[u].push_back(MP(v,w));
G[v].push_back(MP(u,w));
E.PB({u,v});
}
for(int i=1;i<=num;++i){
cin>>route[i][0];
cin>>route[i][1];
}
for(int i=1;i<=n;++i){
dij(i);
}
int res=INF;
for(int i=1;i<=m;++i){
int t=0;
int x=E[i-1][0], y=E[i-1][1];
for(int j=1;j<=num;++j){
int u=route[j][0];
int v=route[j][1];
t+=min({dist[u][v],dist[u][x]+dist[y][v],dist[u][y]+dist[x][v]});
}
chmin(res,t);
}
cout<<res;
return 0;
}