我是靠谱客的博主 哭泣猎豹，最近开发中收集的这篇文章主要介绍Codeforces Round #482 (Div. 2)A - Pizza, Pizza, Pizza!!!B - Treasure HuntC - Kuro and Walking Route，觉得挺不错的，现在分享给大家，希望可以做个参考。
概述
感觉最近状态不是很好，或许是得知了太多事情了，会是新的开始吧，谁知道这条路会通向什么方向呢，眼前的当务之急就是立刻找回状态，迎接即将到来的省赛
A - Pizza, Pizza, Pizza!!!
思路：看似大水题，实则大坑，将一个蛋糕均分成n份，问最少需要几刀
很明显，根据蛋糕的对称性，当n为奇数时，需要切n刀才可
而当n为偶数时，只需要切n/2刀
然而，坑点出现了，如果n为1呢，将一个蛋糕分给一个人吃，显然不需要切啊，然而做题太快完全忽略了这一点
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <map>
#include <cmath>
#include <string>
#include <queue>
#include <stack>
using namespace std;
const int maxn = 1e5+10;
int main()
{
long long n;
while(scanf("%I64d",&n)!=EOF)
{
n++;
if(n==1LL)
{
n=0LL;
}
if(n%2LL==0LL)
{
n /= 2LL;
}
printf("%I64dn",n);
}
return 0;
}
B - Treasure Hunt
思路：这题看似恐怖，像一个大型字符串题，再看一眼数据范围，像是个O（nlog（n））的算法题
然而不难发现，这题其实最优结果一定能用字母表示，于是一切都变得简单了
最后，又是特殊值的处理，一定要警惕了，提交前一定要深思熟虑
这题的其实特殊情况只有一种，那就是当串中所有元素都相同且只有一次操作机会时，是无法达到最大值的
其余情况，只要操作足够，肯定能通过各种玄学操作达到最大值，毕竟人足够聪明
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <map>
#include <cmath>
#include <string>
#include <queue>
#include <stack>
using namespace std;
const int maxn = 1e5+10;
int ku[52],sh[52],ka[52];
int main()
{
int n;
ios::sync_with_stdio(false);
//freopen("in.txt","r",stdin);
while(cin >> n)
{
memset(ku,0,sizeof ku);
memset(sh,0,sizeof sh);
memset(ka,0,sizeof ka);
string Kuro,Shiro,Katie;
cin >> Kuro >> Shiro >> Katie;
int len = Kuro.size();
for(int i=0;i<len;i++)
{
int pos = Kuro[i];
if(pos>='a'&&pos <= 'z')
{
ku[pos-'a']++;
}
else
{
ku[pos-'A'+26]++;
}
pos = Shiro[i];
if(pos>='a'&&pos <= 'z')
{
sh[pos-'a']++;
}
else
{
sh[pos-'A'+26]++;
}
pos = Katie[i];
if(pos>='a'&&pos <= 'z')
{
ka[pos-'a']++;
}
else
{
ka[pos-'A'+26]++;
}
}
int kulen=0,shlen=0,kalen=0;
for(int i=0;i<52;i++)
{
if(ku[i]>kulen)
{
kulen = ku[i];
}
if(sh[i]>shlen)
{
shlen = sh[i];
}
if(ka[i]>kalen)
{
kalen = ka[i];
}
}
//cout << kulen << "*" << shlen << "*" << kalen << "*" << len << "*" << n << endl;
//int lef;
//cout << kulen << "**" << endl;
if(kulen == len&&n==1)
{
kulen--;
}
else
{
kulen += n;
if(kulen >len)
{
kulen = len;
/*lef = len - kulen;
if(lef%2>0)
{
kulen--;
}*/
}
}
if(shlen == len&&n==1)
{
shlen--;
}
else
{
shlen += n;
if(shlen >len)
{
shlen = len;
/*lef = len - shlen;
if(lef%2>0)
{
shlen--;
}*/
}
}
if(kalen == len&&n==1)
{
kalen--;
}
else
{
kalen += n;
if(kalen >len)
{
kalen = len;
/*lef = len - kalen;
if(lef%2>0)
{
kalen--;
}*/
}
}
if(kulen>shlen&&kulen>kalen)
{
cout << "Kuron";
}
else if(shlen>kulen&&shlen>kalen)
{
cout << "Shiron";
}
else if(kalen>kulen&&kalen>shlen)
{
cout << "Katien";
}
else
{
cout << "Drawn";
}
//cout << kulen << "*" << shlen << "*" << kalen << endl << endl;
}
return 0;
}
C - Kuro and Walking Route
思路：这一题看起来也挺吓人的，第一眼觉得可能是最小生成树
又感觉会是最短路dijkstra的一种变体
最终发现，其实也没这么复杂，因为总情况必定为n*（n-1），那么只需要dfs找出连接两个节点的路径，然后统计位于两头的城市数量xnum和ynum
那么结果即为n*（n-1） - xnum*ynum
然而，最后的小bug出现了
位于两边的城市不一定与两个节点直接相连啊，这也是一个dfs的过程，感觉之前似乎犯过这种错误
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <map>
#include <cmath>
#include <string>
#include <queue>
#include <stack>
using namespace std;
const int maxn = 3e5+10;
vector <int> ne[maxn];
bool vis[maxn];
int nep[maxn];
void dfs(int p,int q)
{
int len = ne[p].size();
vis[p] = true;
for(int i=0;i<len;i++)
{
int nowpos = ne[p][i];
if(vis[nowpos])
{
continue;
}
nep[nowpos] = p;
if(nowpos == q)
{
return ;
}
dfs(nowpos,q);
}
return ;
}
void dfsnum(int k,long long &num)
{
vis[k] = true;
int len = ne[k].size();
for(int i=0;i<len;i++)
{
int nowpos = ne[k][i];
if(vis[nowpos])
{
continue;
}
num++;
dfsnum(nowpos,num);
}
return ;
}
int main()
{
int n,x,y;
//freopen("in.txt","r",stdin);
while(scanf("%d%d%d",&n,&x,&y)!=EOF)
{
for(int i=1;i<=n;i++)
{
ne[i].clear();
}
memset(vis,false,sizeof vis);
//memset(len,0,sizeof len);
memset(nep,-1,sizeof nep);
for(int i=1;i<n;i++)
{
int p,q;
scanf("%d%d",&p,&q);
ne[p].push_back(q);
ne[q].push_back(p);
}
if(n==1)
{
printf("0n");
}
else
{
dfs(x,y);
int nepy = nep[y];
int nepx;
for(nepx=y;nep[nepx]!=x;nepx=nep[nepx]);
long long re = (long long)(n) * (long long)(n-1);
long long xnum = 1;
long long ynum = 1;
int xlen = ne[x].size();
int ylen = ne[y].size();
memset(vis,false,sizeof vis);
for(int i=0;i<xlen;i++)
{
int nowpos = ne[x][i];
if(nowpos == y || nowpos == nepx)
{
continue;
}
xnum++;
vis[x] = true;
dfsnum(nowpos,xnum);
}
for(int i=0;i<ylen;i++)
{
int nowpos = ne[y][i];
if(nowpos == x || nowpos == nepy)
{
continue;
}
ynum++;
vis[y] = true;
dfsnum(nowpos,ynum);
}
re -= xnum * ynum;
printf("%I64dn",re);
//cout << xnum << "*" << ynum << endl;
}
}
return 0;
}
最后
以上就是哭泣猎豹为你收集整理的Codeforces Round #482 (Div. 2)A - Pizza, Pizza, Pizza!!!B - Treasure HuntC - Kuro and Walking Route的全部内容，希望文章能够帮你解决Codeforces Round #482 (Div. 2)A - Pizza, Pizza, Pizza!!!B - Treasure HuntC - Kuro and Walking Route所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复