noip2013/day1/1/转圈游戏
2024-09-06 02:08:24
- 总时间限制:
- 10000ms
- 单个测试点时间限制:
- 1000ms
- 内存限制:
- 128000kB
- 描述
-
n 个小伙伴(编号从 0 到 n-1)围坐一圈玩游戏。按照顺时针方向给 n 个位置编号,从 0 到 n-1。最初,第 0 号小伙伴在第 0 号位置,第 1 号小伙伴在第 1 号位置,……,依此类 推。
游戏规则如下:每一轮第 0 号位置上的小伙伴顺时针走到第 m 号位置,第 1 号位置小伙伴走到第 m+1 号位置,……,依此类推,第n − m号位置上的小伙伴走到第 0 号位置,第n-m+1 号位置上的小伙伴走到第1 号位置,……,第 n-1 号位置上的小伙伴顺时针走到第m-1 号位置。
现在,一共进行了 10k 轮,请问 x 号小伙伴最后走到了第几号位置。
- 输入
- 输入文件名为 circle.in。
输入共 1 行,包含 4 个整数 n、m、k、x,每两个整数之间用一个空格隔开。 - 输出
- 输出文件名为 circle.out。
输出共 1 行,包含 1 个整数,表示 10^k 轮后 x 号小伙伴所在的位置编号。 - 样例输入
-
10 3 4 5
- 样例输出
-
5
- 提示
- 对于 30%的数据,0 < k < 7;
对于 80%的数据,0 < k < 10^7;
对于 100%的数据,1 < n< 1,000,000,0 - 来源
- noip2013/day1/第一题
- 数学题注意取mod
-
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = ;
int m;
struct node{
int v,next;
}edge[];int head[maxn],num;
void add_edge(int x ,int y)
{
edge[++num].v=y;edge[num].next=head[x];head[x]=num;
}
bool vis[maxn];int son[maxn];
int siz=0x7fffffff,ans;
void dfs(int x)
{
vis[x]=;
son[x]=;
int tmp=;
for(int i=head[x];i;i=edge[i].next)
{
int v=edge[i].v;
if(vis[v])continue;
dfs(v);
son[x]+=(son[v]+);
tmp=max(son[v]+,tmp);
}
tmp=max(tmp,m-son[x]-);
if(tmp<siz || tmp==siz && ans>x)
{
ans=x;
siz=tmp;
} }
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
memset(vis,,sizeof vis);num=;siz=0x7fffffff;ans=;
memset(head,,sizeof(head));
scanf("%d",&m);
int a,b;
for(int i=;i<m;i++)
{
scanf("%d%d",&a,&b);
add_edge(a,b);add_edge(b,a);
}
dfs();
printf("%d %d\n",ans,siz);
}
return ;
}
最新文章
- sql基础知识:分页+排序
- 获取ip的ip138.com
- 通过Canvas及File API缩放并上传图片完整示例
- nginx反向代理、动静分离
- Android Stutio -- 编译报错: Error:File path too long on Windows, keep below 240
- 【转】PowerShell入门(三):如何快速地掌握PowerShell?
- 制作Linux下程序安装包——使用脚本打包bin、run等安装包
- WPF窗口长时间无人操作鼠标自动隐藏
- MITK Tutorial(二)
- 封装好的PHP分页类,简单好用--在开源看到的,取回来自己用
- spring项目中监听器作用-ContextLoaderListener(项目启动时,加载一些东西到缓存中)
- 第一次AOP,附上使用DEMO,目前只供学习,不可用在生产环境
- 利用python发送邮件
- freemarker中的left_pad和right_pad(十五)
- JavaScript基础入门 - 01
- Springboot Selenide UI 自动化测试
- Electron学习(一)——— electron的安装
- NuGet 使用笔记
- jquery终止函数
- 【Python019--函数与过程】