题意: 相当于均分纸牌，使这几个数的权值相等
分析: 先求出平均数，然后如果大于平均数，直接加上多余的部分，这就是答案
代码:
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10;
int n,tot;
int a[N];
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%d",&a[i]),tot+=a[i];
tot/=n;
int ans=0;
for (int i=1;i<=n;i++)
if(a[i]>tot) ans+=a[i]-tot;
printf("%d\n",ans);
return 0;
}
B Umbrellas for Cows
题意: 将一条数轴上的点都覆盖的最小代价
分析: 假设 f [ i ] 表示将前i个覆盖的最小代价，如果要最小代价，这个伞的左端点肯定是坐标 i 之前的某
一个 j 的坐标,然后他们的距离是 a [ i ] - a [ j ]，所需的伞的最小长度是 a [ i ] - a [ j ] + 1，然而伞的长度和价格没
有关系，也就是说，我们要在a [ i ] - a [ j ] + 1 ~ m 的范围里找一个价格最小的，只需要用一个数组记录一下
代码:
/*
思考：
当前为i，设f[i]表示覆盖前i个点的最小代价
f[i]=min(f[j]+min(c[m-j+1~m])
*/
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m;
int a[N],c[N],st[N],f[N];
int main()
{
memset(f,0x3f,sizeof(f));
scanf("%d%d",&n,&m);f[0]=0;
for (int i=1;i<=n;i++) scanf("%d",&a[i]);
sort(a+1,a+n+1);
for (int i=1;i<=m;i++) scanf("%d",&c[i]);
//价格
st[m+1]=0x3f3f3f3f;c[0]=0x3f3f3f3f;
for (int i=m;i>=0;i--) st[i]=min(st[i+1],c[i]);
for (int i=1;i<=n;i++)
for (int j=i;j>=1;j--)
f[i]=min(f[i],f[j-1]+st[a[i]-a[j]+1]);
printf("%d\n",f[n]);
return 0;
}
C Roadblock
题意: 是某一条边的边权加倍，使原1->n的最短路与现在的最短路差值最大
分析: n范围较小。同时如果要改边，肯定要改最短路上的。不然你改其他路上的，压根就不会走。所以在第一次求
最短路的时候，记录一下转移方向。然后枚举最短路上的边，每改一条就求出当前的最短路，用一个变量记录最大
差值就行啦
代码:
#include<bits/stdc++.h>
using namespace std;
const int N=110,M=11100;
int n,m,tot,ans,cnt;
int f[N],pre[N],las[N],ch[M];
int h[N],nex[M<<1],ver[M<<1],pri[M<<1];
bool vis[N];
inline void add(int x,int y,int z)
{
nex[tot]=h[x];
ver[tot]=y;
pri[tot]=z;
h[x]=tot++;
}
inline void spfa()
{
memset(f,0x3f,sizeof(f));
f[1]=0;
queue<int>q;
q.push(1);vis[1]=1;
while(!q.empty())
{
int k=q.front();q.pop();
for (int i=h[k];~i;i=nex[i])
{
int j=ver[i];
if(f[j]>f[k]+pri[i])
{
pre[j]=k,las[j]=i;
f[j]=f[k]+pri[i];
if(!vis[j])
vis[j]=1,q.push(j);
}
}vis[k]=0;
}
}
int main()
{
memset(h,-1,sizeof(h));
scanf("%d%d",&n,&m);
for (int i=1;i<=m;i++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
add(x,y,z),add(y,x,z);
}
spfa();
int now=n;
while(now!=1)
{
ch[++cnt]=las[now];
now=pre[now];
}
int li=f[n],ans=0;
for (int i=1;i<=n;i++)
{
pri[ch[i]]*=2;
pri[ch[i]^1]*=2;
spfa();
ans=max(ans,f[n]-li);
pri[ch[i]]/=2;
pri[ch[i]^1]/=2;
}
printf("%d\n",ans);
return 0;
}
D Cow Photography(Silver)
分析: 一个结论题。假设有A，B两头奶牛，因为每头奶牛最多只移动一次，且最多只会改变两次先后顺序。即第一
次，奶牛B会换到A前面，第二次A可能又会换到B前面。那么通俗来说，只要有三张照片里，A的位置在B之前，那
么原来A就在B前面
代码:
#pragma GCC optimize(3,"inline","Ofast","fast-math","no-stack-protector","unroll-loops")
#pragma GCC target("sse","sse2","sse3","sse4","avx","avx2","popcnt")
#include<bits/stdc++.h>
using namespace std;
const int N=2e4+10;
int n;
int a[N];
map<int,int> k[6];
inline bool god(int x,int y)
{
int num=0;
for (int i=1;i<=5;i++)
if(k[i][x]<k[i][y]) num++;
if(num>=3) return 1;
return 0;
}
int main()
{
scanf("%d",&n);
for (int i=1;i<=5;i++)
for (int j=1;j<=n;j++)
{
int x;scanf("%d",&x);
a[j]=x;
k[i][x]=j;
}
sort(a+1,a+n+1,god);
for (int i=1;i<=n;i++) printf("%d\n",a[i]);
return 0;
}
E Grass Planting
题意：使某一条路径上的所有路的权值加一，然后询问某一条边的权值
分析：感jio树链剖分是可以做。但是有另一种方法。通过题意，发现这很像差分。那么我们用dfs序记录每个节点
被遍历到的顺序，每次给边+1的时候，因为能管到的区域，是从lca到x点，lca到y点之间的路径，这个时候给将这
两个之间的路径-1，因为lca部分减了两次，加上2
代码：
//#pragma GCC optimize(3,"inline","Ofast","fast-math","no-stack-protector","unroll-loops")
//#pragma GCC target("sse","sse2","sse3","sse4","avx","avx2","popcnt")
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#define RG register
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;
const int N=1e5+10;
int n,m,cnt,tot;
int f[N][21],dep[N],d[N];
int a[N],L[N],R[N],head[N];
struct nkl
{
int nex,to;
}e[N<<1];
inline void add(int x,int y)
{
e[++cnt].nex=head[x];
e[cnt].to=y;
head[x]=cnt;
}
inline void dfs(int u,int pre)
{
dep[u]=dep[pre]+1;
f[u][0]=pre;
L[u]=++tot;
for (int i=1;i<=18;i++)
f[u][i]=f[f[u][i-1]][i-1];
for (int i=head[u];i;i=e[i].nex)
{
int v=e[i].to;
if(v==pre) continue;
dfs(v,u);
}
R[u]=tot;
}
inline int LCA(int x,int y)
{
if(dep[x]<dep[y]) swap(x,y);
for (int i=18;i>=0;i--)
if(dep[f[x][i]]>=dep[y])
x=f[x][i];
if(x==y) return x;
for (int i=18;i>=0;i--)
if(f[x][i]!=f[y][i])
x=f[x][i],y=f[y][i];
return f[x][0];
}
inline int lowbit(int x)
{
return x&(-x);
}
inline void ad(int i,int k)
{
while(i<=n)
{
d[i]+=k;
i+=lowbit(i);
}
}
inline int get(int i)
{
int ans=0;
while(i>0)
{
ans+=d[i];
i-=lowbit(i);
}
return ans;
}
int main()
{
cin>>n>>m;
for (int i=1;i<n;i++)
{
int x,y;
cin>>x>>y;
add(x,y),add(y,x);
}
dfs(1,0);
while(m--)
{
char ins;int x,y;
cin>>ins;
cin>>x>>y;
if(ins=='P')
{
int lca=LCA(x,y);
ad(L[x],1);
ad(L[y],1);
ad(L[lca],-2);
}
else
{
if(dep[x]<dep[y]) x=y;
printf("%d\n",get(R[x])-get(L[x]-1));
}
}
return 0;
}
F Simplifying the Farm
似乎是最有价值的一道题。
/*
对于这样一棵重边很少的生成树
重边要么取,要么不取,先找重边,然后
取出可以加入的边的数量,然后通过乘
法原理求解
*/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=4e4+10,M=1e5+10;
const ll mod=1e9+7;
int n,m;
int f[N];
struct nkl
{
int u,v;ll p;
bool operator < (const nkl &b)const
{
return p<b.p;
}
}s[M];
inline int find(int x)
{
if(x==f[x]) return x;
return f[x]=find(f[x]);
}
int main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=m;i++)
scanf("%d%d%lld",&s[i].u,&s[i].v,&s[i].p);
sort(s+1,s+m+1);
for (int i=1;i<=n;i++) f[i]=i;
ll ans=0,num=1;
for (int i=1;i<=m;)
{
int j;
set<pair<int,int> >t;
ll cnt=0,sum=0;
for (j=i;j<=m;j++)
{
int u=find(s[j].u),v=find(s[j].v);
if(u>v) swap(u,v);
if(u!=v)
{
cnt++;
t.insert(make_pair(u,v));
}
if(s[j].p!=s[j+1].p) break;
}//相同权值的边数量
for (;i<=j;i++)
{
int u=find(s[i].u),v=find(s[i].v);
if(u!=v)
{
f[v]=u;
sum++;
ans+=s[i].p;
}
}//已加入的边的数量
if(sum==1) num=num*cnt%mod;
//只有一条，随便加
if(sum==2)
{
if(cnt==3&&t.size()==2) num=num*2%mod;
//有等价边,
if(cnt==3&&t.size()==3) num=num*3%mod;
//无等价边,
}
}
printf("%lld %lld\n",ans,num);
return 0;
}
G Cow Photography
和D题一样
H Cow Beauty Pageant (Bronze)
分析：直接求出两个连通块中的点，如果要连接，那肯定是其中最近的两个点的距离减-1
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=55;
int n,m,tot,ans=0x3f3f3f3f;
int a[N][N],cnt[N];
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
bool vis[N][N];
struct nkl
{
int dx,dy;
};
nkl k[5][N*N/3];
inline bool check(int x,int y)
{
return x<1||x>n||y<1||y>m;
}
inline void bfs(int x,int y)
{
tot++;
queue<int>u,v;
u.push(x),v.push(y);
vis[x][y]=1;
while(u.size())
{
int x=u.front(),y=v.front();
u.pop(),v.pop();
k[tot][++cnt[tot]].dx=x,k[tot][cnt[tot]].dy=y;
for (int i=0;i<4;i++)
{
int xx=x+dx[i],yy=y+dy[i];
if(check(xx,yy)) continue;
if(vis[xx][yy]) continue;
if(!a[xx][yy]) continue;
vis[xx][yy]=1;
u.push(xx),v.push(yy);
}
}
}
int main()
{
cin>>n>>m;
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
{
char c;cin>>c;
if(c=='X') a[i][j]=1;
}
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
{
if(!a[i][j]) continue;
if(vis[i][j]) continue;
bfs(i,j);
}
for (int i=1;i<=cnt[1];i++)
for (int j=1;j<=cnt[2];j++)
ans=min(ans,abs(k[1][i].dx-k[2][j].dx)+abs(k[1][i].dy-k[2][j].dy));
printf("%d\n",ans-1);
return 0;
}
I Moo Sick
题意：求出一个序列A中有多少子段和序列B相似。这里的相似定义存在某一个数，使B数组同时加上他时，所有的
数是A的某一个子段
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=2e4+10;
int n,c,tot;
int a[N],k[N],b[N],ans[N];
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++) scanf("%d",&a[i]);
scanf("%d",&c);
for (int i=1;i<=c;i++) scanf("%d",&k[i]);
sort(k+1,k+c+1);
for (int i=1;i<=n;i++)
{
int cnt=0;
if(i+c-1>n) break;
for (int p=i+c-1;p>=i;p--) b[++cnt]=a[p];
sort(b+1,b+cnt+1);
bool ok=0;
for (int p=2;p<=cnt;p++)
if(k[p]-b[p]!=k[p-1]-b[p-1]) ok=1;
if(!ok) ans[++tot]=i;
}
printf("%d\n",tot);
for (int i=1;i<=tot;i++) printf("%d\n",ans[i]);
return 0;
}
J Awkward Digits
代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=100;
int cnt;
char a[N],b[N],c[N];
inline bool check(ll ok,int bb)
{
cnt=0;
while(ok)
{
c[cnt++]=(ok%3+'0');
ok/=3;
}
int num=0;
if(cnt!=bb) return 0;
for (int i=0;i<bb;i++)
if(c[i]!=b[bb-i-1]) num++;
if(num==1) return 1;
return 0;
}
int main()
{
scanf("%s%s",a,b);
int lena=strlen(a),lenb=strlen(b);
ll now=0;
for (int i=0;i<lena;i++) now=now*2+(a[i]-'0');
for (int i=1;i<lena;i++)
{
int c=a[i]-'0';
ll th=now-c*(1<<(lena-i-1))+(c^1)*(1<<(lena-i-1));
if(check(th,lenb))
{
printf("%lld\n",th);
return 0;
}
}
return 0;
}
K Contest Timing
分析：数据不大，直接求出所有的分钟数，相减就行
代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a,b,c;
int main()
{
scanf("%lld%lld%lld",&a,&b,&c);
ll las=1440*11+11*60+11;
ll now=1440*a+b*60+c;
if(now-las<0) puts("-1");
else printf("%lld\n",now-las);
return 0;
}
Tile Exchanging
分析：本来以为我的暴力程序不会过的，结果....我直接记录f [ i ] [ j ] 表示前i个矩形使面积为 j 的最小
代价，然后三重循环，第一层当前编号，第二层构成面积，第三层，边长
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=14,M=1e4+10;
int n,m;
int a[N],f[N][M];
int main()
{
memset(f,0x3f,sizeof(f));f[0][0]=0;
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++) scanf("%d",&a[i]);
sort(a+1,a+n+1);
for (int i=1;i<=n;i++)
{
for (int j=1;j<=m;j++)//枚举面积
for (int k=1;k<=100;k++)//枚举边长
{
if(k*k>j) break;
f[i][j]=min(f[i][j],f[i-1][j-k*k]+(a[i]-k)*(a[i]-k));
}
}
if(f[n][m]>1e9) puts("-1");
else printf("%d\n",f[n][m]);
return 0;
}
京公网安备 11010502036488号