CCPC 2017-2018, Finals 一些题解
发布时间
阅读量：
阅读量
C - Rich Game
题目设置有些让人困惑的地方。
解法是计算二分队伍最多能赢得多少局数，并且必须确保赢得足够多的局数且不出现亏损的情况。
特别地，在每次比赛时，若输掉一局所损失的资金少于所获分数值，则无需担心总分会减少。
A - Dogs and Cages
这是一道基础题。求一个序列随机排列之后，在原来位置上的期望值是多少？
对于每个数字而言，在其正确位置的情况数为n!减去(n-1)!种情况；共有n个这样的数字，则符合条件的情况总数为n \times (n! - (n-1)!)种情况；因此总的期望值即为\frac{n \times (n! - (n-1)!)}{n!}化简后得到的结果就是n-1。
F - Fair Lottery
这一轮的表现让人有些意外……
这是一道基础题：只需将每个数字乘以1.1并向上取整后再相加即可得到最终结果。
G - Alice’s Stamps
这道题目本质上是一个动态规划问题：我们定义dp[i][j]表示前i张邮票分成j组的最佳方案；每一步都可以选择将当前邮票加入到最后一组中或开始新的组别中，并根据这两种选择的结果取最优解即可完成整个过程的建模与计算。
#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
进行预计算（打表），特别需要注意的是，在走棋过程中可能会出现重复访问的点。通过分析规律得出结论：最大值通常在约12^18的数量级附近。为了避免溢出问题，在C++编程中通常会使用unsigned long long类型来处理较大的数值范围。当棋盘边长n小于等于4时，在中心区域尚未完全填充的情况下（a direct output of the precomputed table结果）.
#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 System 涉及这道题属于差分约束问题。通过分析题目要求明确变量之间的关系。
- 当A等于B并且C也等于D时，则有D减A至少为x，并且C减B至多为x。
- 当A不相等与B并且C也不相等与D时，则有D减A严格大于x，并且C减B严格小于x；这表明任何两站之间的距离都不会正好是x。
- 当A相等但C与之不同则会发现D减去A严格大于x同时C减去相应位置的距离必定小于x。
- 此外，在任何两相邻车站之间都存在一个间隔：i与i+1之间的距离至少为1。
- 实质上就是分两种情况进行讨论。
- 然后我们对这些不等式进行了标准化处理，并计算最短路径（最长路径），这取决于我们的建模方法。
- 构建差分约束系统的核心挑战在于如何有效地设置这些约束关系。
#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
询问在修改一次之后基环树上的着色块数量。
看到时间限制似乎很有吸引力。因此我们需要寻找一种高效的方法而不是暴力枚举所有可能性。
我们考虑这样一个问题：如何高效地计算每个顶点周围不同颜色的数量？
对于树结构中的每条边（即不在环中的边），它们会被计入两次；而对于环中的每条边，则会被计入两次。
如果我们想要计算这个答案的总和，则需要考虑连通性因素：因为每个顶点最多连接两条边，在计数过程中可能会多算次数而形成额外的结果差异（即所谓的连通快数目）。
因此，在树结构中答案为\sum f_i - (n-1)；而在环结构中则为\sum f_i - n；特别地，在环上仅有一种颜色的情况下（即所有相邻顶点颜色相同），答案还需要额外加1以修正计数偏差。
#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;
}全部评论 (0)
还没有任何评论哟~