C - Rich Game
题意有点坑。
解法是二分会赢多少局，只要满足赢若干局而且不会输钱的条件就行，注意如果每次得分输的钱比失分得的钱少，那么就是全部胜利了。
A - Dogs and Cages
水题。求一个序列随机排列之后，还在原来位置上的期望。
对于一个数来说，在自己位置上的情况数是n! - (n-1)!,一共有n个数，总共有n!种情况，答案就是n ∗ ( n ! − ( n − 1 ) ! ) n ! {n * (n! - (n-1)!)} \over n!n!n∗(n!−(n−1)!) 化简一下就是n-1
F - Fair Lottery
黑了一波Goden Bear还行……
水题，读完题之后就是每个数乘1.1向上取整求个和
G - Alice’s Stamps
这道题就其实就是个dp,用dp[i][j] 代表前i个邮票，选择k个set的最优方案，首先每个方案都可以被拆分，那我们我们维护每个邮票最多能向右延伸多少距离，然后分不增加答案和增加答案两种情况考虑。
#include <bits/stdc++.h>
#include <bitset>
#define ll long long
#define INF 0x3f3f3f3f
#define pr pair<int,int>
#define fi first
#define next fuck
#define se second
using namespace std;
const int maxn = 2002;
int dp[maxn][maxn];
int rt[maxn];
int main()
{
int ca,cat = 1;
cin>>ca;
while(ca--)
{
int n,m,k;
cin>>n>>m>>k;
memset(dp,0,sizeof(dp));
memset(rt,0,sizeof(rt));
for(int i = 0;i<m;i++)
{
int l,r;
cin>>l>>r;
rt[l-1] = max(rt[l-1],r - l + 1);
}
for(int i = 1;i<n;i++)
{
rt[i] = max(rt[i],rt[i-1] -1);
}
for(int i = 0;i<n;i++)
{
for(int j = 0;j<=k;j++)
{
dp[i+1][j] = max(dp[i+1][j],dp[i][j]);
dp[i][j+1] = max(dp[i][j+1],dp[i][j]);
dp[i + rt[i]][j+1] = max(dp[i + rt[i]][j+1],dp[i][j]+rt[i]);
}
}
printf("Case #%d: %d\n",cat++,dp[n][k]);
}
return 0;
}
K - Knightmare
强行打表，注意打表的时候要注意可以走重复的点。找到规律发现最大值大概有12e18左右，要开unsigned long long 才能过,当n <= 4 的时候中心区域没有填满，需要直接输出打表的结果
#include <bits/stdc++.h>
#include <cstring>
#define ll unsigned long long
using namespace std;
int x,y,k;
ll a[10] = {1,9,41,109};
int main()
{
//freopen("input.txt","r",stdin);
int T;
scanf("%d",&T);
for(int cas=1;cas<=T;++cas)
{
ll n;
scanf("%I64u",&n);
ll ans;
if(n < 4) ans = a[n];
else
{
ans = 2*(n + 1 + n+ 2);
ans += (4*n -1) *(2*n + 1);
ans += (n-2)*(2*n+3+4*n-3);
}
printf("Case #%d: %I64u\n",cas,ans);
}
return 0;
}
J - Subway Chasing
这是一道差分约束的题，根据题意我们可以先把ABCD的关系搞清楚
- 如果 A = B 且C = D : D - A >= x，C - B <= x
- 如果 A!=B 且 C !=D : D - A > x , C - B< x. 也就是说两个站中间差的绝对不会等于X
- 如果 A=B 且 C != D : D - A > x , C - B < x
- 还有注意两个车站之间一定有一个间隔：i - (i + 1) >= 1
其实就是分成两种情况了，然后我们对不等式进行标准化，跑一边最短路（最长路，取决于建图方式
差分约束唯一的难点就在于怎么建图,要注意从0开始跑最短路。
#include <bits/stdc++.h>
#include <bitset>
#define ll long long
#define pr pair<int,int>
#define fi first
#define next fuck
#define se second
using namespace std;
const int MAXN=2010;
const int INF=0x3f3f3f3f;
struct Edge
{
int v;
int cost;
Edge(int _v=0,int _cost=0):v(_v),cost(_cost) {}
};
vector<Edge>E[MAXN];
void addedge(int u,int v,int w)
{
E[u].push_back(Edge(v,w));
}
bool vis[MAXN];//在队列标志
int cnt[MAXN];//每个点的入队列次数
int dist[MAXN];
bool SPFA(int start,int n)
{
memset(vis,false,sizeof(vis));
fill(dist,dist+n+1,INF);
memset(cnt,0,sizeof(cnt));
vis[start]=true;
dist[start]=0;
queue<int>que;
while(!que.empty())
que.pop();
que.push(start);
cnt[start]=1;
while(!que.empty())
{
int u=que.front();
que.pop();
vis[u]=false;
for(int i=0; i<(int)E[u].size(); i++)
{
int v=E[u][i].v;
if(dist[v]>dist[u]+E[u][i].cost)
{
dist[v]=dist[u]+E[u][i].cost;
if(!vis[v])
{
vis[v]=true;
que.push(v);
if(++cnt[v]>n)
return false;
//cnt[i]为入队列次数，用来判定是否存在负环回路
}
}
}
}
return true;
}
int n,m,x;
int main()
{
int ca,cat = 1;
scanf("%d",&ca);
while(ca--)
{
scanf("%d%d%d",&n,&m,&x);
for(int i =0; i<=n + 1; i++)
{
E[i].clear();
}
for(int i = 1; i<=n; i++)
{
if(i < n)
addedge(i+1,i,-1);
addedge(0,i,0);
}
for(int i = 0; i<m; i++)
{
int a,b,c,d;
scanf("%d%d%d%d",&a,&b,&c,&d);
if(a == b)
{
if( c == d)
{
addedge(d,a,-x);
addedge(b,c,x);
}
else
{
addedge(d,a,-x-1);
addedge(b,c,x-1);
}
}
else
{
addedge(d,a,-x-1);
addedge(b,c,x-1);
}
}
printf("Case #%d:",cat++);
if(SPFA(0,n+1))
{
for(int i = 2; i<=n; i++)
{
printf(" %d",dist[i] - dist[i-1]);
}
}
else
printf(" IMPOSSIBLE");
printf("\n");
}
return 0;
}
I - Inkopolis
求一个基环树上在一次修改之后的色块个数
看到时限的确有点心动。所以怎么暴力呢？
我们思考这样一个问题，假设我们暴力计数每个点连接的边的不同颜色的数量，每一条边会被加多少次？
在树上的边：那么除了连接环的一条边，剩下的边都被加了两次。
在环上的边：所有的边都加了两次。
如果我们想知道这个答案的总和，事实上和连通性并没有关系，因为在计数过程中，颜色的联通会直接反应在数量上，因为一个点最多有两条边，对于第一种情况我们减去多算的次数，就是联通快的数量。
所以答案是这样组成的,设f[i]是一个点周围的变得颜色数量：
在树上的答案∑ f i − ( n − 1 ) \sum f_i - (n-1)∑fi−(n−1)
在环上的答案∑ f i − n \sum f_i - n∑fi−n
当然对于环上只有一种颜色的情况，答案要加一
#include <cstdio>
#include <map>
#include <iostream>
#define ll long long
#define pr pair<int,int>
#define mp make_pair
#define fi first
#define next fuck
#define se second
using namespace std;
const int MAXN = 2e5 + 10;
template <class T> inline bool read(T &ret)
{
char c;
int sgn;
if(c=getchar(),c==EOF)
return 0;
while(c!='-'&&(c<'0'||c>'9'))
c=getchar();
sgn=(c=='-')?-1:1;
ret=(c=='-')?0:(c-'0');
while(c=getchar(),c>='0'&&c<='9')
ret=ret*10+(c-'0');
ret*=sgn;
return 1;
}
struct Edge
{
int to,next,w;
}edge[MAXN*2];
map<pr,int> E;
map<int,int> V[MAXN];
map<int,int> loop;
int in[MAXN];
int head[MAXN],tot;
int vis[MAXN],pre[MAXN],prew[MAXN];
bool flag ;
int n,m;
void init(int n)
{
E.clear();
for(int i = 0; i<=n; i++)
{
head[i] = -1;
vis[i] = 0;
in[i] = 0;
V[i].clear();
}
loop.clear();
tot= 0;
flag = 0;
}
void addege(int u,int v,int w)
{
edge[tot].to = v;
edge[tot].w = w;
edge[tot].next = head[u];
head[u] = tot++;
}
void dfs(int u,int p)
{
if(flag) return;
vis[u] = 1;
for(int i = head[u]; i!= -1;i = edge[i].next)
{
int v =edge[i].to;
if(v == p) continue;
if(!vis[v])
{
pre[v] = u;
prew[v] = edge[i].w;
dfs(v,u);
}
else
{
flag = 1;
int now = u;
loop[edge[i].w]++;
in[v] = 1;
while(now != v)
{
in[now] = 1;
loop[prew[now]] ++;
now = pre[now];
}
}
if(flag) return;
}
}
int main()
{
int ca,cat = 1;
read(ca);
while(ca--)
{
int u,v,w;
read(n),read(m);
init(n+1);
for(int i = 0;i<n;i++)
{
read(u),read(v),read(w);
E[mp(u,v)] = w;
E[mp(v,u)] = w;
V[u][w]++;
V[v][w]++;
addege(u,v,w);
addege(v,u,w);
}
dfs(1,1);
int cnt = 0;
int lsize = loop.size();
for(int i = 1;i<=n;i++)
{
cnt += V[i].size();
}
cnt -= n;
printf("Case #%d:\n",cat++);
while(m--)
{
read(u),read(v),read(w);
int ww = E[mp(u,v)];
E[mp(u,v)] = w;
E[mp(v,u)] = w;
if(-- V[u][ww] == 0) cnt--;
if(-- V[v][ww] == 0) cnt--;
if(++ V[u][w] == 1) cnt++;
if(++ V[v][w] == 1) cnt++;
if(in[v] && in[u])
{
if(--loop[ww] == 0 ) lsize--;
if(++loop[w] == 1) lsize++;
}
if(lsize == 1)
printf("%d\n",cnt+1);
else
printf("%d\n",cnt);
}
}
return 0;
}
版权声明：本文为lingzidong原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。