和@tkj666大佬双排，可惜我太菜了，大佬带不动
A. Computer Game
题意
给定2∗n的01方格，初始从(0,0)开始，只能走0格子，问是否能走到(2,n)
输入保证(0,0)和(2,n)为0格子
T≤100
n≤100
解法
只需检查起点和终点是否连通即可
复杂度O(n)
Key Point
四连通，行数为n，若存在一列上的两格均为1则不连通
Code
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
| #include <bits/stdc++.h>
using namespace std;
const int maxn=100+5;
int T;
int n;
char s[2][maxn];
int vst[2][maxn];
int ans=0;
bool Work()
{
memset(vst,0,sizeof(vst));
scanf("%d",&n);
scanf("%s%s",s[0],s[1]);
for(int i=0;i<n;++i)
{
if(s[0][i] == '1' && s[1][i]=='1')
return false;
}
return true;
}
int main()
{
scanf("%d",&T);
while(T--)
{
if(Work())
{
puts("YES");
}
else
{
puts("NO");
}
}
}
|
B. Groups
题意
有偶数n个学生，每个学生在工作日的若干天有空，问是否能把这些学生分成等量的两组，使得组内的所有人均在同一天有空
T≤104
n≤1000
∑n≤105
解法
暴力枚举两天，计算这两天中仅第一天有空，仅第二天有空和两天都有空的学生数量，记为a,b,c
满足题意的a,b,c应满足a≤n/2,b≤n/2,a+b+c=n
复杂度O(n)
Code
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
| #include <bits/stdc++.h>
using namespace std;
const int maxn=1000+5;
int T;
int n;
int con[maxn][10];
bool Solve(int fir,int sec)
{
int fs=0,ss=0,bs=0;
for(int i=1;i<=n;++i)
{
fs+=con[i][fir] && !con[i][sec];
ss+=con[i][sec] && !con[i][fir];
bs+=con[i][fir] && con[i][sec];
}
if(fs+ss+bs==n && fs<=n/2 && ss<=n/2)
{
return true;
}
else
return false;
}
void Work()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
for(int j=1;j<=5;++j)
scanf("%d",&con[i][j]);
for(int i=1;i<=5;++i)
for(int j=i+1;j<=5;++j)
{
if(Solve(i,j))
{
puts("YES");
return;
}
}
puts("NO");
}
int main()
{
scanf("%d",&T);
while(T--)
{
Work();
}
}
|
C. Delete Two Elements
我是傻逼
题意
给定数组a，设其均值为k（可能为小数），问有多少对数满足删除这对数后，数组均值不变
T≤104
3≤n≤2⋅105
∑n≤2⋅105
解法
显然这样的数对的平均值为k
只需对所有数减去k，计算相反数有多少对即可
Key Point
细节之处在于，k可以为小数
但我们可以对所有数乘上n从而避免进行除法运算
同时要注意单独处理0的情况
Code
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
| #include <bits/stdc++.h>
using namespace std;
const int maxn=200000+100;
int T;
int n;
long long a[maxn];
void Work()
{
scanf("%d",&n);
long long ave = 0;
for(int i=1;i<=n;++i)
{
scanf("%lld",&a[i]);
ave+=a[i];
a[i]*=n;
}
for(int i=1;i<=n;++i)
a[i]-=ave;
long long ans=0;
long long zero=0;
sort(a+1,a+n+1);
for(int i=1;i<=n;++i)
{
if(a[i]==0)
{
++zero;
continue;
}
ans+=upper_bound(a+1,a+n+1,-a[i])-lower_bound(a+1,a+n+1,-a[i]);
}
printf("%lld\n",ans/2+zero*(zero-1)/2);
}
int main()
{
scanf("%d",&T);
while(T--)
{
Work();
}
}
|
D. Training Section
题意
给定n个数对(ai,bi)，**保证互异（即没有两个数对的a,b同时相等）**从中选择三个成为一个三元组。定义合法三元组满足如下条件
- ai两两不同，或
- bi两两不同
计算合法三元组的条件
解法
可以先算三元组个数，再减去不合法三元组的个数
三元组个数显然为\C^{3}_{n}
再考虑不合法三元组，由于数对各异，因此不合法三元组应为以下形态：
(x1,y1),(x1,y2),(x2,y2)
考察“中心数对”（即(x1,y2)），则能够与它形成这样的不合法三元组的数量应为(cnt(x1)−1)∗(cnt(y2)−1)
直接从答案中减去即可
复杂度O(n)
Code
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
| #include <iostream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long ll;
template<typename T>void read(T &t)
{
t=0;int f=0;char c=getchar();
while(!isdigit(c)){f|=(c=='-');c=getchar();}
while(isdigit(c)){t=t*10+c-'0';c=getchar();}
if(f)t=-t;
}
const int maxn=200000+100;
int T;
int n;
int a[maxn],b[maxn];
int cnta[maxn],cntb[maxn];
void Work()
{
read(n);
for(int i=1;i<=n;++i)
{
read(a[i]);
read(b[i]);
cnta[i]=0;
cntb[i]=0;
}
for(int i=1;i<=n;++i)
{
cnta[a[i]]++;
cntb[b[i]]++;
}
ll ans=1LL*n*(n-1)*(n-2)/6;
for(int i=1;i<=n;++i)
{
ans-=1LL*(cnta[a[i]]-1)*(cntb[b[i]]-1);
}
printf("%lld\n",ans);
}
int main()
{
read(T);
while(T--)
{
Work();
}
return 0;
}
|
先写这么多吧
