【清北学堂国庆刷题班】 Day1
T1 打扑克
题目描述
皮蛋为了讨好黑妞，想要跟她打扑克。
他们打的扑克是这样一种规则：有面值大小从1到n的扑克各一张。其中奇数牌在皮蛋手中，偶数牌在黑妞手中。每人每次只能出一张牌，先出完者获胜（遵循最基本的扑克规则：当对手出牌后，可以选择出一张比他大的牌，或者不管，让他再任意出一张牌）。假设皮蛋和黑妞都是足够聪明的人，都想让自己获胜。现在给定n和谁先出牌，那么谁会获胜呢？
输入格式
第1行1个正整数T，表示数据组数。
接下来T行，每行2个正整数n,op，表示打一局牌。其中n如题所示，保证op∈{0,1}，op=0表示皮蛋先出牌，op=1表示黑妞先出牌。
输出格式
T行每行1个数表示打一局牌的答案。0表示皮蛋获胜，1表示黑妞获胜。
样例数据
input
output
数据规模与约定
对于 40%的数据，n≤10。
对于 70% 的数据，n≤10000。
对于 100% 的数据,2≤n≤101000,T≤100。
时间限制：1s
空间限制：512MB
思路
这道题主要是找规律
分类讨论，对于这个题目，可以这么讨论：
-
n为偶数时
<1>n=2 op=0
当n等于二的时候当然就是一下子就出完了。
<2>n>2
比如n=4的时候，有1，2，3，4四张牌
皮蛋有1，3，黑妞有2，4
op=0时，皮蛋先出牌，发现皮蛋不管怎么出都是输
op=1时，同理
经过许许多多实验发现除了当n为偶数的时候（除n=2外），皮蛋总是输
2.n为奇数时
比如n=5的时候，有1，2，3，4，5五张牌
皮蛋有1，3，5，黑妞有2，4
op=0时，皮蛋先出牌，皮蛋出3，黑妞出4，皮蛋出5，黑妞出不了，皮蛋再出一个1，这样皮蛋就出完了，经过非常多的时间，根据不完全归纳法，我们可以判定n为奇数且皮蛋先出牌的时候可以获胜
op=1时，黑妞先出牌，发现皮蛋怎么出都是输
讨论完毕
因此当n等于2且op=0的时候或者n为奇数且op=0时皮蛋可以获胜，因为n有亿点大，所以要用字符串输入，判断后两位是奇数还是偶数即可
代码
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
| #include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
long long T;
int main()
{
cin>>T;
while(T--)
{
char s[1005];
long long n;
scanf("%s",s);
n=(s[strlen(s)-2])*10+s[strlen(s)-1]-'0';
int op;
cin>>op;
if(n==2)
{
cout<<op<<endl;
continue;
}
else if(n%2==1&&op==0)
cout<<0<<endl;
else cout<<1<<endl;
}
return 0;
}
|
T2 粉刷匠
题目描述
皮蛋喜欢黑妞，想为她粉刷一面网格墙。
墙上有n行m列共n∗m个网格。初始时，整面墙都是红色的。皮蛋只有红、蓝两种颜色的油漆，而且皮蛋很懒，他每次刷墙只会把某一整行或某一整列刷成红色或蓝色。皮蛋一共粉刷了k次墙。现在给出皮蛋的粉刷方案，请你求出最后这面墙有多少个格子是蓝色的。
输入格式
第1行3个正整数n,m,k。
接下来k行，每行3个整数x,y,z表示一次刷墙。保证x,z∈{0,1}x,z∈{0,1}，x=0表示皮蛋粉刷第y行，否则表示粉刷第y列；z=0则表示将该行（列）的格子都粉刷成红色，否则表示都粉刷成蓝色。保证操作合法。
输出格式
1行1个数表示答案。
样例数据
input
output
数据规模与约定
对于 30%的数据，1≤n,m,k≤1000
对于另外 30%的数据，n≤10,1≤m,k≤1000000
对于 100% 的数据，1≤n,m,k≤100000
时间限制：2s
空间限制：512MB
思路
这道题主要是一个思考方式的问题，如果从正面思考，来考虑有多少个方块，双重循环，这样时间复杂度严重超标，因此我们考虑到倒着进行循环
倒着循环可以设一个数组，来标记一下这一行或者这一列有没有被粉刷过，如果被粉刷过就不再计算了，如果没有被粉刷过，就加上这一行或者这一列的列数或者行数，然后删除这一列或者这一行，不再计算，因为是倒着考虑的，所以不用担心其他的操作
代码
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
| #include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
#define N 1000010
#define M 1010
using namespace std;
int n[2],k;
int x[N],y[N],z[N];
bool vi[2][N];
ll ans;
int main()
{
cin>>n[0]>>n[1]>>k;
for(int i=1;i<=k;i++) scanf("%d%d%d",&x[i],&y[i],&z[i]);
for(int i=k;i;i--)
if(!vi[x[i]][y[i]])
{
vi[x[i]][y[i]]=true;
if(z[i]) ans+=n[!x[i]];
n[x[i]]--;
}
cout<<ans<<endl;
return 0;
}
|
T3 直线竞速
题目描述
一年一度的繁荣山庄直线竞速比赛要开始了！
本次比赛共有n位选手，第i位选手的起点在ai位置，速度是vi，速度方向是正方向。
之后有Q个询问，每次询问经过t秒后，排名在第k位的选手的编号（在相同位置时，编号小的排名靠前）。
输入格式
第1行1个正整数n。
接下来n行，每行2个正整数vi,ai。
接下来1行1个整数Q。
接下来Q行，每行2个正整数t,k表示一个询问。
输出格式
Q行，每行一个整数表示询问的答案。
样例数据
input
1
2
3
4
5
6
7
8
9
10
| 4
2 100
3 50
4 60
5 1
4
1 1
50 2
60 4
100 1
|
output
数据规模与约定
对于 30%的数据，1≤n,Q≤1000
对于另外40%的数据,k=1
对于100% 的数据，1≤n,Q≤7000,1≤t≤109,1≤vi,ai≤105,1≤k≤n
时间限制：2s
空间限制：512MB
思路
这道题目看到的第一思路是暴力，对于每个询问计算一个位置，然后进行排序，直接输出第k位选手的编号，但是这个时间复杂度比较大，为O(nQlogn),数据显然会超时，所以我们在这个上面进行改善。
仔细观察上面的步骤，我们可以使用分治求第k小元素，这样我们可以在O(n)的时间内算出来排名第k的选手的编号了
代码
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
| #include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
#define dd double
#define ll long long
#define N 7010
#define M 1010
using namespace std;
int n,Q;
struct ma
{
int v,a,num;
}w[N];
bool cmp1(ma x,ma y)
{
return x.a>y.a;
}
struct am
{
int t,k,ans,num;
}q[N];
bool cmp2(am x,am y)
{
return x.t<y.t;
}
bool cmp3(am x,am y)
{
return x.num<y.num;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
scanf("%d%d",&w[i].v,&w[i].a);
w[i].num=i;
}
cin>>Q;
for(int i=1;i<=Q;i++)
{
scanf("%d%d",&q[i].t,&q[i].k);
q[i].num=i;
}
sort(w+1,w+n+1,cmp1);
sort(q+1,q+Q+1,cmp2);
for(int i=0;i<=Q;i++)
{
for(int j=1;j<=n;j++)
{
for(int k=j;k>1;k--)
{
ll x=w[k].a+(ll)w[k].v*q[i].t;
ll y=w[k-1].a+(ll)w[k-1].v*q[i].t;
if(y<x||y==x&&w[k-1].num>w[k].num) swap(w[k-1],w[k]);
else break;
}
}
q[i].ans=w[q[i].k].num;
}
sort(q+1,q+Q+1,cmp3);
for(int i=1;i<=Q;i++) printf("%d\n",q[i].ans);
return 0;
}
|
T4 游戏
题目描述
有一个游戏：给定两个正整数序列A,B，长度分别为n,m。你可以做如下操作：删掉A的最后x(x≥1)个数并得到它们的和S1，同时删掉B的最后(y≥1)个数并得到它们的和S2，这次操作的花费是(S1–x)(S2–y)。你需要一直操作直到A,B都为空（不能做完一次操作后使得其中一个为空而另一个非空）。本次游戏的总花费是每次花费的和。求最小的总花费。
输入格式
第1行2个正整数n,m。
第2行n个正整数，表示序列A。
第3行m个正整数，表示序列B。
输出格式
1行1个数表示最小的总花费。
样例数据
input
output
数据规模与约定
数据点1：n=20，m=20。
数据点2：n=110，m=80。
数据点3：n=200，m=130。
数据点4：0n=400，m=80。
数据点5：n=1000，m=333。
数据点6：n=510，m=910。
数据点7：n=1200，m=1400。
数据点8：n=700，m=1800。
数据点9：n=1998，m=1370。
数据点10：n=2000，m=1999。
对于100% 的数据，1≤Ai,Bi≤1000
时间限制：2s
空间限制：512MB
思路
没有思路
说实话，这道题看到了之后我是非常地懵逼的。看到了题解之后。。。
动态规划！
用f[i][j]来表示A的前i个数和B的前j个数做游戏，最小的总花费。
然后用SA和SB两个数组存一下A序列和B序列的前缀和
就有状态转移方程：
F[i][j]=min(f[k][r]+(SA[i]−SA[k])∗(SB[j]−SB[r]))
´其中
0≤k<i,0≤r<j
但是时间复杂度还是比较大为O(m2n2)，因此我们需要继续简化
经过推算发现，如果存在一个最优解的话，那么至少有一段删的数字长度为1，那么我们可以重新定义状态
´f[i][j][0]表示A的最后一段长度为1，……
´f[i][j][1]表示B的最后一段长度为1，……
这样就可以得到正确答案了。
代码
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<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define dd double
#define ll long long
#define N 2010
#define M 1010
using namespace std;
int n,m;
int a[N],b[N];
int f[N][N],g[N][N];
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
a[i]--;
}
for(int i=1;i<=m;i++)
{
scanf("%d",&b[i]);
b[i]--;
}
memset(f,0x3f,sizeof(f));
memset(g,0x3f,sizeof(g));
f[0][0]=g[0][0]=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
int x=a[i]*b[j];
f[i][j]=min(f[i][j-1],min(f[i-1][j-1],g[i-1][j-1]))+x;
g[i][j]=min(g[i-1][j],min(f[i-1][j-1],g[i-1][j-1]))+x;
}
int ans=min(f[n][m],g[n][m]);
cout<<ans<<endl;
return 0;
}
|
总结
对于这一套题目，主要考了找规律，有技巧的暴力，分治法和动态规划，对于解题方法不是非常地熟练，但是这些方法真的都非常重要，因此以后再复习以及训练的时候要多练一些基础算法题目，然后再次基础上拓展，逐渐达到难题（NOI）的水平
