A
一个环，分成k端，每段的值是所有数|起来，总值是所有端&起来。输出最大值
B
一张有自环、重边的有向图，边的耗时都为1
前k个点有生产机器，每个点j在 x*k+j 时刻产生一个产品(x>=0)
一条路在某刻只有一个产品，路口不限产品数，
问前k个点可以留下那几台机器，使满足所有产品都能被运到第n个点
C
题意
给出n个区间[ s_i , t_i ]，问这些区间总覆盖数字多少个
数据范围
n<100, si,ti<365
题解
前缀和维护，然后暴力看一下那些数字有值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| #include<bits/stdc++.h>
using namespace std;
int const maxn=400;
int qwq[maxn],sum[maxn];
int main(){
int n;
scanf("%d",&n);
int a,b;
for(int i=1;i<=n;i++){
scanf("%d%d",&a,&b);
qwq[a]+=1,qwq[b+1]-=1;
}
int ans=0;
for(int i=1;i<=365;i++){
sum[i]=sum[i-1]+qwq[i];
if(sum[i]>0)ans++;
}
printf("%d\n",ans);
return 0;
}
|
D
题意：
给出一张无向图（可能还有多个连通块），如果1个点感染病毒，他可以感染它邻居的邻居，你可以在一些点之间加边。问最少加几条边可以使最初感染一个点后扩散到所有点都被感染。
题解：
一个连通块内，如果含有一个奇环（环由奇数个点构成），就能感染整个连通块。
所以只要判断图中有几个连通块，有没有一个连通块中含有奇环。先把所有连通块联通，没有奇环的话多花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
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
69
70
| #include<bits/stdc++.h>
using namespace std;
int const maxn=5e5+10;
int tot,head[maxn],n,m,val[maxn],f[maxn],se[maxn];
bool vis[maxn];
struct edge{
int v,nxt;
}e[maxn<<1];
void build(int x,int y){
e[++tot].v=y;
e[tot].nxt=head[x];
head[x]=tot;
}
void prime(){
for(int i=1;i<=n;i++)
f[i]=i;
}
int find(int x){
if(f[x]==x)return f[x];
f[x]=find(f[x]);
return f[x];
}
void merge(int x,int y){
int f1=find(x),f2=find(y);
f[f1]=f2;
}
bool you=1;
void ranse(int x){
vis[x]=1;
if(you==0)return ;
for(int i=head[x];i;i=e[i].nxt){
int v=e[i].v;
if(vis[v]){
if(se[x]==se[v]){
you=0;return ;
}
}
else se[v]=1-se[x];
}
for(int i=head[x];i;i=e[i].nxt){
int v=e[i].v;
if(!vis[v])ranse(v);
}
}
int main(){
scanf("%d%d",&n,&m);
prime();
tot=0;
memset(head,0,sizeof(int)*(n+5));
int a,b;
for(int i=1;i<=m;i++){
scanf("%d%d",&a,&b);
build(a,b);
build(b,a);
merge(a,b);
}
int ans=0;
for(int i=1;i<=n;i++){
if(find(i)==i){
ans++;
ranse(i);
}
}
printf("%d\n", ans-1+you);
return 0;
}
|
E
给n个点，求选3个点，最大的三角形面积。
题解：
凸包+旋转卡壳
F
给定字符串s，可以改变最多k次s中的字符，如果改动后的字符串中出现连着三个或以上的相同字符，这一串字符会变为 * ，问最多让几个字符最后变为 * 。
G
题意
问某个数的非质因子有多少个
题解：
预处理欧拉筛法质因子分解（记录每个数第一次被那个数筛掉），假设一个数x的m个质因子次数分别为 a1,a2....am
ans= (a1+1)*(a2+1)...(am+1)-m
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
|
#include<bits/stdc++.h>
using namespace std;
int const maxn=2000010;
int prime[maxn],s[maxn];
int cntprime = 0;
bool flag[maxn];
void euler(){
for (int i = 2; i < maxn; i++){
if (!flag[i]) prime[++cntprime] = i;
for (int j = 1; j <= cntprime && prime[j] * i < maxn; j++){
flag[i * prime[j]] = true;
s[i*prime[j]]=prime[j];
if (i % prime[j] == 0)
break;
}
}
}
int main(){
int t;
scanf("%d",&t);
int a,b;
euler();
for(int i=1;i<=t;i++){
scanf("%d",&a);
if(flag[a]==0){
printf("1\n");
continue;
}
int ans=1,cou=0,v=sqrt(a);
while(s[a]){
cou++;
int tot=0,v=s[a];
while(a%v==0){
tot++;
a/=v;
}
ans*=(tot+1);
}
if(a>1){ans*=2;cou++;}
printf("%d\n",ans-cou);
}
return 0;
}
|
比赛:
别暴力质因数分解啊！！
H
给出初始字母s，每个字母有一个替换规则，进行k次替换。
m次询问，问替换完后某个位置的数是多少
l
在r*c的矩形中，选n次子矩形，这些子矩形都至少含有k个相同的格子。问有多少种方案，某一次选的格子不同即为一种不同方案。
J
K
L
在序列中找字典序最小的A B A B
哈哈哈
哈哈哈