足球比赛

描述
在2009的中国城市足球比赛中,在2^N支队中,有一些队在开赛前宣布了退出比赛。比赛采取的是淘汰赛。比如有4支队伍参加,那么1队和2队比赛,3队和4队赛,然后1队和2队的胜者与3队和4队的胜者争夺冠军。但是由于某些队伍退出,那么如果某个原本存在的比赛只有一个支队,那么这一支队自动晋级,如果没有队伍出现,那么就跟本没有比赛。比如,1队和2队退出比赛,那么就只有3队和4队的比赛,然后其胜者在原本和1队和2队的胜者的决赛中自动晋级,成为冠军。
给出哪些队退出的比赛计算会有多少场比赛中队伍自动晋级。
输入
第一行有两个数N(1<=N<=10),M。接下来有M个数,表示哪些队退出了比赛。选手编号从1到2
输出
在第一行输出有多少场比赛中队伍自动晋级。
输入样例 1
2 2
3 4
输出样例 1
1
输入样例 2
3 5
1 2 3 4 5
输出样例 2
2
输入样例 3
2 1
2
输出样例 3
1

思路

像建立一个二叉树一样,如果只有一个子树return 0 ,那么意味着另一个子树的队伍直接晋级

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <set>
#include <math.h>
#include <algorithm>
#define maxn 55
using namespace std;

int node[1030]={0};
int kkk=0;

int build(int left,int right,int k){
int mid=(left+right)/2;
if(left==right){
return !node[left];
}
int lll=build(left,mid,2*k);
int rrr=build(mid+1,right,2*k+1);
if(lll==0&&rrr!=0||lll!=0&&rrr==0){
kkk++;
return 1;
}
else if(lll==0&&rrr==0){
return 0;
}
else{
return 1;
}
}


int main(){

int n,m;
scanf("%d%d",&n,&m);
int sum=1;
for(int i=1;i<=n;i++) sum*=2;
for(int i=1;i<=m;i++){
int x;
scanf("%d",&x);
node[x]=1;
}
build(1,sum,1);
printf("%d",kkk);
return 0;
}

奇怪的贸易

描述
刚结束了CS战斗的小D又进入了EVE的游戏世界,在游戏中小D是一名商人,每天要做的事情就是在这里买东西,再运到那里去卖。这次小D来到了陌生的X星,X星上有n种货物,小D决定每种都买走一些,他用ai来表示第i种货物购买的数量,X星人对物品的单价有特别的决定方式。他们首先会选择一个基本价x,第一种物品单价为x,第二种物品单价为x2,第三种物品单价为x3……第i种物品单价为xi.结算总价时,你还需要给他们一笔手续费a0,小D不知道自己带的钱是否能够进行这笔交易,所以请你帮助他计算这笔交易他要支付的总金额是多少。
输入
x n
a0
a1
a2
.
.
.
an
第一行两个数分别表示基准价x (x<=10),物品种数n (n<=100000)
第二行一个数,手续费a0 (a0<=100)
接下来的n行每行一个数,第i行表示第i种物品购买的数量(ai<=100)
输出
输出结果的最后100位,若不足100位请高位用零补足
输入样例 1
2 3
4
3
2
1
输出样例 1
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000026
提示
【数据规模】对20%的数据:n<=10 对50%的数据:n<=200 对100%的数据:n<=100000

思路

大数精确(使用数组模拟乘法)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <set>
#include <math.h>
#include <algorithm>
using namespace std;


int a[100005];
int b[101];
int c[101]={0};

int main(){
int aaa,n;
scanf("%d%d",&aaa,&n);
int all;
scanf("%d",&all);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
b[100]=all;
c[100]=aaa;
for(int j=1;j<=n;j++){
int t=0;
for(int i=100;i>=1;i--){
b[i]=b[i]+a[j]*c[i]+t;
t=b[i]/10;
b[i]=b[i]%10;
}
t=0;
for(int i=100;i>=1;i--){
c[i]=c[i]*aaa+t;
t=c[i]/10;
c[i]%=10;
}
}

for(int i=1;i<=100;i++){
printf("%d",b[i]);
}


return 0;
}

营养膳食

描述
阿月正在女朋友宁宁的监督下完成自己的增肥计划。
为了增肥,阿月希望吃到更多的脂肪。然而也不能只吃高脂肪食品,那样的话就会导致缺少其他营养。阿月通过研究发现:真正的营养膳食规定某类食品不宜一次性吃超过若干份。比如就一顿饭来说,肉类不宜吃超过1份,鱼类不宜吃超过1份,蛋类不宜吃超过1份,蔬菜类不宜吃超过2份。阿月想要在营养膳食的情况下吃到更多的脂肪,当然阿月的食量也是有限的。
输入
输入,第一行包含三个正整数n(n≤200),m(m≤100)和k(k≤100)。表示阿月每顿饭最多可以吃m份食品,同时有n种食品供阿月选择,而这n种食品分为k类。第二行包含k个不超过10的正整数,表示可以吃1到k类食品的最大份数。接下来n行每行包括2个正整数,分别表示该食品的脂肪指数ai和所属的类别bi,其中ai≤100,bi≤k。
输出
输出,包括一个数字即阿月可以吃到的最大脂肪指数和。
输入样例 1
6 6 3
3 3 2
15 1
15 2
10 2
15 2
10 2
5 3
输出样例 1
60

思路

贪心 对各个种类的食物排序然后按大小依次选择

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <set>
#include <math.h>
#include <algorithm>
using namespace std;

int food[205][205];
int times[205];
int kkk[205];

int main()
{

int n,m,k;
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=k;i++) scanf("%d",&times[i]);
for(int i=1;i<=n;i++){
int q,p;
scanf("%d%d",&p,&q);
kkk[q]++;
food[q][kkk[q]]=p;
}
for(int i=1;i<=k;i++){
sort(food[i]+1,food[i]+kkk[i]+1);
}
int sum=0;
int sss=0;
for(int i=1;i<=m;i++){
int maxx=0;
for(int j=1;j<=k;j++){
if(maxx<food[j][kkk[j]]&&times[j]>0){
maxx=food[j][kkk[j]];
sss=j;
}
}
kkk[sss]--;
sum+=maxx;
times[sss]--;
}
printf("%d\n",sum);
return 0;
}

魔术棋子

描述
在一个MN的魔术棋盘中,每个格子中均有一个整数,当棋子走进这个格子中,则此棋子上的数会被乘以此格子中的数。一个棋子从左上角走到右下角,只能向右或向下行动,请问此棋子走到右下角后,模(mod)K可以为几?
如以下2
3棋盘:
344
566
棋子初始数为1,开始从左上角进入棋盘,走到右下角,上图中,最后棋子上的数可能为288,432或540。所以当K=5时,可求得最后的结果为:0,2,3。
输入
输入第一行为三个数,分别为M,N,K (1≤M,N,K≤ 100)
以下M行,每行N个数,分别为此方阵中的数。
输出
输出第一行为可能的结果个数 第二行为所有可能的结果(按升序输出)
输入样例 1
2 3 5
3 4 4
5 6 6
输出样例 1
3
0 2 3

思路

dfs就可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<bits/stdc++.h>
#define ll long long
#define DB double
using namespace std;
int n,m,k,a[200][200];
bool v[120][120][120],use[200];
int ans[200*200],l,rx,ry;
int dx[]={1,0},dy[]={0,1};
ll tmp;
void dfs(int x,int y,int h)
{
if(v[x][y][h]) return;
// cout<<x<<" "<<y<<" "<<h<<endl;
v[x][y][h]=1;
if(x==n && y==m)
{
if(!use[h]) ans[++l]=h,use[h]=1;
return;
}
for(int i=0;i<=1;++i)
{
rx=x+dx[i];ry=y+dy[i];
if(rx<1 || rx>n || ry<1 || ry>m) continue;
tmp=1ll*h*a[rx][ry]%(ll)k;
dfs(rx,ry,(int)tmp);
}
}
int main()
{
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
scanf("%d",&a[i][j]);
dfs(1,1,a[1][1]);
cout<<l<<endl;
sort(ans+1,ans+l+1);
for(int i=1;i<=l;++i) cout<<ans[i]<<" ";
return 0;
}

123法典

描述
很久很久以前,有个叫123的国家,这个国家的国王很喜欢颁布各种法令,并把这些法令记录在一部《123法典》中。最近这部法典终于被发掘了出来,专家们经过研究发现法典中的法令是按颁布的时间顺序记载的只有两种格式:

同时,如果一条法令没有被其他有效的法令宣布无效,那么它就是有效的。现在他们想知道那些法令是有效的,你能帮助他们吗?
输入
第一行一个数N,表示法典中法令的数目。
接下来N行每行一个字符串,表示一条法令,第i行的法令编号为i。法令按颁布时间顺序给出。
输出
第一行一个数K表示有效法令的数目。
第二行K个数表示有效法令的编号,两个数中间用一个空格隔开。
输入样例 1
5
declare
cancel 1
declare
cancel 2
cancel 3
输出样例 1
3
1 4 5
输入样例 2
3
declare
declare
declare
输出样例 2
3
1 2 3
提示
【数据规模】
对于全部的数据,N <= 100000。

思路

从后往前遍历 假如后者否决前者 就直接忽略

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <set>
#include <math.h>
#include <algorithm>
using namespace std;

int a[100005]={0};
int b[100005]={0};


int main(){
int n;
char s[100];
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%s",s);
if(s[0]=='c'){
int x;
scanf("%d",&x);
b[i]=x;
}
}
int sum=0;
for(int i=n;i>=1;i--){
if(b[i]&&a[i]==0){
a[b[i]]--;
}
}
for(int i=1;i<=n;i++){
if(a[i]>=0) sum++;
}
printf("%d\n",sum);
for(int i=1;i<=n;i++){
if(a[i]>=0) printf("%d ",i);
}


return 0;
}

数字游戏

大家列队后,都觉得累了,于是一起坐到院子中的草地上休息。这时Anna突然想跟她的最大竞争对手Cici玩一个数字游戏,她要你编写程序帮助她取得胜利。
第i次游戏初始时有一个整数N_i(1 <= N_i <= 1,000,000),,游戏以Anna先开始,然后是Cici,这样两人轮流进行。在每一轮中,一个游戏者可以把当前整数中减去原整数中最大的数字或最小的非零数字,形成一个新的整数。例如从3014开始,我们可以减去1或4,分别形成整数3013或3010.直到这个整数变为0时游戏结束。游戏结束时最后轮到那人就是胜利者。
Anna和Cici总共进行G(1 <= G <= 100)次游戏。请你帮助确定每次游戏到底是Anna还是Cici获得胜利。Anna和Cici两人都是足够聪明的,如果轮到某人时,对方留给她的数是必胜的,她将毫不犹豫按最优策略取得胜利。
假如某次游戏N_i=13。Anna先走并从中减去3,剩下10,然后Cici只能减去1,剩下9,Anna减去9,剩下0游戏结束,Anna取得这次游戏的胜利。
输入
第1行:一个整数G 第2..G+1行:第i+1行包含一个整数: N_i
输出
*第1..G行:第i行包含”YES”,表示Anna取得第i次游戏的胜利,否则为”NO”。
输入样例 1
2
9
10
输出样例 1
YES
NO

思路

简单博弈,前者推后者的两个状态假如全是必胜点 那么就为必败点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>
#include <stdio.h>
#include <string.h>
#define maxn 1000005
using namespace std;

bool SG[maxn];

int maxx(int a){
int max=0;
while(a){
if(max<a%10) max=a%10;
a/=10;
}
return max;
}

int minn(int a){
int min=9;
while(a){
if(a%10!=0){
if(min>a%10) min=a%10;
}
a/=10;
}
return min;
}



int main(){
int k,m;
scanf("%d",&k);
for(int i=10;i<maxn;i++){
int mmm=maxx(i),nnn=minn(i);
if(!SG[i-mmm]&&!SG[i-nnn]){
SG[i]=true;
}
}
for(int i=0;i<k;i++){
scanf("%d",&m);
if(!SG[m]) printf("YES\n");
else printf("NO\n");
}
return 0;
}

附 SG函数的模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int f[N],SG[N];
bool S[M];
void getSG(int n)
{
memset(SG,0,sizeof(SG));
for(int i=1;i<=n;i++)
{
memset(S,false,sizeof(S));
for(int j=1;f[j]<=i&&j<M;j++)
{
S[SG[i-f[j]]]=true;
}
while(S[SG[i]]) SG[i]++;
}
}

捉迷藏

Anna正在和一群朋友在玩捉迷藏游戏。这种游戏由若干人一起玩,其中一个人为“鬼”,其他人藏在N个房间,由鬼来找这些人。Anna想计算出N(2 <= N <= 20,000)个房间(编号为1……N)中她应该藏哪一间?
Anna知道“鬼”会从房间1开始找。所有房间被M条双向路连接M (1<= M <= 50,000),这种双向路以(A_i,B_i)表示,其中1<=A_i<=N;1<=B_i<=N; A_i!=B_i。通过这些双向路,任意两个房间之间都可以到达。
Anna觉得离房间1最远的那个房间最安全(相邻两个房间之间的距离为1),请你帮Anna编写一个程序找出她应该躲在哪个房间。
输入
第一行为N和M;第2行至第M+1行,分别包含一条路(A_i,B_i)。
输出
仅有一行,包含三个整数I、J、K,分别表示Anna应该躲的房间号(如果有多解,输出编号最小的)、房间1到Anna躲的房间的距离、Anna可以躲的房间数目。
输入样例 1
6 7
3 6
4 3
3 2
1 3
1 2
2 4
5 2
输出样例 1
4 2 3

思路

用bfs进行搜索 并用set存储各个房间的位置 不然容易超时

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <queue>
#include <set>
#define maxn 20002
using namespace std;

//bool mmp[maxn][maxn];
struct node{
bool vis;
int depth;
int num;
node(){
vis=false;
depth=0;
}
}b[maxn];
int s,start=0;
int n,m;
int maxx=0;

bool cmp(const node &a,const node &c){
return a.depth>c.depth;
}

int main(){
set<int>mmp[maxn];

scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
int x,y;
scanf("%d%d",&x,&y);
mmp[x].insert(y);
mmp[y].insert(x);
}
for(int i=1;i<=n;i++){
b[i].num=i;
}
queue<node>Q;
node a,now;
Q.push(b[1]);
b[1].vis=true;
while(!Q.empty()){
now=Q.front();
Q.pop();
if(now.depth>b[s].depth){
s=now.num;
start=1;
}
else if(now.depth==b[s].depth){
start++;
if(s>now.num) s=now.num;
}
set<int>::iterator iter = mmp[now.num].begin();
while (iter!=mmp[now.num].end()){
if(!b[*iter].vis){
b[*iter].depth=now.depth+1;
b[*iter].vis=true;
Q.push(b[*iter]);
}
iter++;
}
}
printf("%d %d %d\n",s,b[s].depth,start);

return 0;
}

photos

最后更新: 2019年03月28日 23:39

原始链接: http://yoursite.com/2019/03/27/ACM训练赛/ACM训练赛/

× 请我吃糖~
打赏二维码