Codeforces Round #328 (Div. 2)
tags: Codeforces
难得题目不难,结果比赛的时候C题差一分钟没交上去,不然怎么着都能涨个百来分啊(T_T)
A. PawnChess
题意:
给定一个8*8的棋盘,有W,B两种棋子,W只能往上走,B只能往下走,由W先走.若(任意一个)W先到达棋盘边缘,输出A,若B先到达棋盘边缘,输出B.题目保证一定有结果.
解析:
对于每个W往上找有没有其他棋子,若没有,则能到达边缘,记录所有能到达边缘的W到离边缘距离的最小值
minW
.对于B同理,得到
minB
然后比较两个值大小即可,注意相等时输出A.
代码:
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
using namespace std;
char mp[10][10];
int main()
{
for (int i = 0; i < 8; i++)
{
scanf("%s",mp[i]);
}
int stepa = 100;
int stepb = 100;
for (int i = 0; i < 8; i++)
{
for (int j = 0; j < 8; j++)
{
if (mp[i][j] == 'W')
{
int k;
for (k = i-1; k >= 0; k--)
{
if (mp[k][j] != '.')
break;
}
if (k < 0 && (i < stepa))
stepa = i;
}
else if (mp[i][j] == 'B')
{
int k;
for (k = i+1; k < 8; k++)
{
if (mp[k][j] != '.')
break;
}
if (k >= 8 && ((7 - i) < stepb))
stepb = (7 - i);
}
}
}
printf("%c\n", stepa <= stepb ? 'A' : 'B');
return 0;
}
B. The Monster and the Squirrel
题意:
一个正n(n>=3)边型,从每个顶点向其他顶点发出射线,每条射线会被已存在的射线截止.问至少需要跨越多少条线段才能访问包括多边形外的所有区域.
解析:
显而易见,跳跃次数最小为平面上区域数-1,我们可以计算出平面上区域数目从而得到结果.而每条射线将使区域数增加1,因此区域数=(射线数+2),这也就是说跳跃次数=射线条数+1.
然后就是数射线数目,从图上可以发现,除了1,2,n这三个点有n-3条线段外,其他点只有(n-4)条.所以一共是3 (n-3)+(n-3)(n-4)即(n-3)(n-1)条射线,加上1之后输出即可,使用__int64防爆.
代码:
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
using namespace std;
int main()
{
__int64 n;
scanf("%I64d",&n);
__int64 ans = (n - 3)*(n-1)+1;
printf("%I64d\n",ans);
return 0;
}
C. The Big Race
比赛的时候爆__int64了好几次,好不容易改对了结果一看时间已经结束一分钟了orz
题意:
两个人赛跑,一个人步长为w,另一个为v,赛道长度为L,跑的距离大于L时将掉入深渊.问在[1,t]范围内有多少个L使得这两个人无法分出胜负(同时落入深渊),记为tie.以tie/t形式输出(约分,使其满足gcd(tie,t)==1).
解析:
实际上是找
[1,t]
范围内有多少个数满足
L(modw)≡L(modv)
,即满足
w∗x+r=v∗y+r
的个数.
即
lcm(w,v)∗k+r
从上式可以得到,每
lcm(w,v)
个数会是一个循环,每个循环内最多有
min(w,v)
个满足等式的值,因此我们只要求出
lcm(w,v)
,然后所有满足(
1≤lcm(w,v)∗k+r≤t,且r<min(w,v)
)的个数就是我们要求的tie的个数.
例如对于37 3 4这组输入
lcm(3,4)=12
,故循环节长度为12,循环个数为37/12+1=4,而m=min(3,4)=3,每个循环最多3个满足条件的
第一个循环0~11,符合式子的有0,1,2 (0需要舍弃)
第二个循环12~23,符合式子的有12,13,14
第三个循环24~35,符合式子的有24,25,26
第四个循环36~37,符合式子的有36,37
可见除了最后一组外,其他循环都有m个(算上0的话),因此可以先统计前t/lcm(u,v)组,一共有t/lcm(u,v)*m-1个(去掉0).然后最后一组的个数为min(t%lcm(u,v)+1,m)个,相加即得到平局的L的个数,然后和输出tie/t的化简形式即可.
有需要注意的地方:
-
lcm(w,v)∗k
和r同时为0的情况(也就是L=0的时候)应该去掉
- 第11个测试TLE其实是运算过程中爆__int64了,导致gcd()函数参数为负数
- 由于
lcm(w,v)
会爆__int64,我们可以先用double暂存,然后根据其与t的大小关系进行后续处理.
代码和题解不是同一天写的,故代码和题解表述略有不同,不过应该不影响理解
代码:
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
using namespace std;
#define MIN(a,b) ((a) < (b)) ? (a) : (b);
__int64 gcd(__int64 a, __int64 b)
{
while (b ^= a ^= b ^= a %= b);
return a;
}
int main()
{
__int64 t, u, v;
scanf("%I64d%I64d%I64d", &t, &u, &v);
__int64 m = MIN(u, v);
__int64 g = gcd(u, v);
double lcm = (double)(u / g) *v;
__int64 k ;
if (lcm > t)
{
k = MIN(t,m-1);
}
else
{
k = (t / (__int64)lcm) *m;
k += MIN(t % (__int64)lcm, m - 1);
}
__int64 gg = gcd(k, t);
printf("%I64d/%I64d\n", (k / gg),(t / gg));
return 0;
}
//5000000000000000000 4000000000000000000 5000000000000000000
D. Super M
题意:
给一棵树,其中有些点遭到了攻击,问从哪一点开始可以用最短的时间访问所有被攻击的点,并输出最少需要多少单位时间(每经过一条边消耗1单位时间).
解析:
首先,我们实际要经过的边只包含在包含所有被攻击点的最小子树中.我们需要先求出这棵子树,然后假设从某个被攻击的A点开始(显然要选被攻击的点作为起点),访问其他所有被攻击的点,最后到达另一个被攻击的点B,则连接AB两点路径上的边将被访问一次,其余支路上的边需要访问两次(A到B的路上一点->被攻击点->A到B的路上同一点),因此访问这棵子树需要的时间是子树边数*2 - A到B路径上的边.子树边数固定,要让时间最小,应让A到B的长度最长,也就是说应取这棵树的直径(树上最长路径).
从而题目转化为:从给定的树中提取出对应的子树,然后求其直径,需要的时间是子树边数*2 - 子树直径,同时输出直径(可能有多条直径)对应端点中最小的点即可.
求子树的过程可以通过一次dfs完成,而求树直径的方法可以参考这篇文章.由于本鶸dp方面几乎和没学过差不多,所以就选择两发bfs()搜索的方法来确定树的直径.
代码:
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
using namespace std;
#define MIN(a,b) ((a) < (b)) ? (a) : (b)
#define MAXN 123456+100
int n, m;
int index_min;
vector<int> T[MAXN];
vector<int> E[MAXN];
bool attacked[MAXN];
bool vis[MAXN];
struct NodeType
{
NodeType() {};
NodeType(int i, int s) :idx(i), step(s) {}
int idx;
int step;
}farest;
bool dfs(int s)
{
vis[s] = true;
int flag = false;
for (int i = 0; i < T[s].size(); i++)
{
int u = T[s][i];
if (!vis[u])
{
if (dfs(u))//若可以从s向u走到达被攻击的点,则将边(s,u)加入子树
{
E[s].push_back(u);
E[u].push_back(s);
flag = true;
}
}
}
if (flag || attacked[s])
return true;
return false;
}
void bfs(int s)
{
memset(vis, 0, sizeof(vis));
queue<NodeType> que;
vis[s] = true;
farest.idx = MAXN;
farest.step = 0;
que.push(NodeType(s,0));
while (!que.empty())
{
NodeType node = que.front();
if (attacked[node.idx])
{
if (node.step > farest.step)
{
farest.idx = node.idx;
farest.step = node.step;
}
else if (node.step == farest.step && node.idx < farest.idx)
farest.idx = node.idx;
}
int sz = E[node.idx].size();
for (int i = 0; i < sz; ++i)
{
if (!vis[E[node.idx][i]])
{
que.push(NodeType(E[node.idx][i], node.step + 1));
vis[E[node.idx][i]] = true;
}
}
que.pop();
}
}
int main()
{
memset(attacked, 0, sizeof(attacked));
scanf("%d%d",&n,&m);
for (int i = 1; i < n; i++)
{
int a, b;
scanf("%d%d", &a, &b);
T[a].push_back(b);
T[b].push_back(a);
}
int k=0;
for (int i = 0; i < m; i++)
{
scanf("%d", &k);
attacked[k] = true;
}
memset(vis, 0, sizeof(vis));
dfs(k); //建立包含所有被攻击点的子树
bfs(k);
int s = farest.idx;
bfs(s);
int t = farest.idx;
int max_len = farest.step;
int sum_len = 0;
for (int i = 1; i <= n; i++)
{
sum_len += E[i].size();
}
printf("%d\n", MIN(s, t));
printf("%d\n", sum_len - max_len); //求sum_len的时候每条边被数了两次,可以直接拿来用
return 0;
}
E. BCPC
还没做
