北京信息科技大学第十一届程序设计竞赛
感觉没有吉首大学那场好玩。
老年选手智商尽失,勉勉强强刷刷水题维持生活。
A kotori和糖果
卡了一天,made竟然是个煞笔题,用map取重剪去搜索节点就可以了,但竟然还会爆INT????
题意:n堆石头,每堆一个,合并的代价是两堆数量差值。求合并成一堆最小代价。
分析:哈夫曼合并树模型,容易推出公式f(n)=f(n/2)+f((n+1)/2)+(n&1),但对于n=1e18运算节点太多重复太多,所以用map处理。
1 | #include<bits/stdc++.h> |
B kotori和气球
题意:n中颜色数量不限的气球,选m个摆成一排,相同颜色不能相邻,方案数对109取余。
分析:ans=n*(n-1)*(n-1)* *** *(n-1)
1 | #include<bits/stdc++.h> |
C kotori和出道
题意:n个人始终成一个环,依次报数,偶数出列,求最后剩下的人是谁。
分析:经典约瑟夫环问题。但这题打个表规律就出来了。
1 | import math |
D kotori和迷宫
题意:意思就是从起点开始搜,到了出口’e’就直接出去,求能到达的出口数量和最近出口的距离。
分析:在广搜的基础上加一句即可,判断当前点是否为出口’e’,是直接continue
。
1 | #include<bits/stdc++.h> |
E kotori和素因子
- 题意:n≤10个数,每个数≤1000。从每个数中选出一个素因子,要求所选出的所有素因子不同。求这些素因子的和的最小值。
- 分析:正解是暴搜即可。1000以内的数每个数由最多5个素因子之积组成,那么暴力的复杂度是510=9765625。
- 题解2:费用流模型。源点0到[1-n]这n个数分别建边容量为1,费用为0;n个数每个数分别与它的素因子建边,容量为1,费用为0(或1,这样素因子到汇点的费用为0即可);素因子到汇点T建边,容量为1,费用为素因子大小。
- 想想看这样为什么费用流模型可以?费用流模型在最大流的基础上求最小费用,流量自然是我们这n个数每个数都要选一个,我们给每个数i都创建流量为1的通路,那么最终最大流量就是n,不到n输出-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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f;
const int N=1e3+10;
struct Edge
{
int to,next,cap,flow,cost;
} e[N*10];
int head[N],tot,tn;
int pre[N],dis[N];
int vis[N];
void init(int num)
{
tot=0;//边的数量
tn=num;
memset(head,-1,sizeof(head));
}
void add(int u,int v,int cap,int cost)
{
e[tot].to=v,e[tot].cap=cap,e[tot].cost=cost,e[tot].flow=0;
e[tot].next=head[u];
head[u]=tot++;
e[tot].to=u,e[tot].cap=0,e[tot].cost=-cost,e[tot].flow=0;
e[tot].next=head[v];
head[v]=tot++;
}
bool spfa(int s,int t)
{
queue<int>q;
for(int i=0; i<=tn; i++)
{
dis[i]=INF;
vis[i]=0;
pre[i]=-1;
}
dis[s]=0;
vis[s]=1;
q.push(s);
while(!q.empty())
{
int u=q.front();
q.pop();
vis[u]=0;
for(int i=head[u]; i+1; i=e[i].next)
{
int v=e[i].to;
if(e[i].cap>e[i].flow&&dis[v]>dis[u]+e[i].cost)
{
dis[v]=dis[u]+e[i].cost;
pre[v]=i;
if(!vis[v])
{
vis[v]=1;
q.push(v);
}
}
}
}
if(pre[t]==-1) return false;
return true;
}
void mincost_maxflow(int s,int t,int n)
{
int cost=0;
int flow=0;
while(spfa(s,t))
{
int Min=INF;
for(int i=pre[t]; i!=-1; i=pre[e[i^1].to])
if(Min>e[i].cap-e[i].flow)
Min=e[i].cap-e[i].flow;
for(int i=pre[t]; i!=-1; i=pre[e[i^1].to])
{
e[i].flow+=Min;
e[i^1].flow-=Min;
cost+=e[i].cost*Min;
}
flow+=Min;
}
if(flow<n||flow>=INF) puts("-1");
else printf("%d\n",cost);
}
int prime[1003],Vis[1003];
int a[50];
int main()
{
int n,cnt=0;
memset(prime,-1,sizeof(prime));
prime[0]=prime[1]=0;
for(int i=2; i<=1000; i++)
if(prime[i])
{
for(int j=i*i; j<=1000; j+=i)
prime[j]=0;
prime[cnt++]=i;
}
while(~scanf("%d",&n))
{
memset(Vis,0,sizeof(Vis));
int Cnt=0;
for(int i=1; i<=n; i++)
{
scanf("%d",&a[i]);
for(int j=0; j<cnt; j++)
if(a[i]%prime[j]==0&&Vis[prime[j]]==0)
Vis[prime[j]]=++Cnt;
}
init(1+n+Cnt+2);
for(int i=1; i<=n; i++)
{
add(0,i,1,0); //源点到i
for(int j=0; j<cnt; j++)
if(a[i]%prime[j]==0)
add(i,n+Vis[prime[j]],1,prime[j]); //i到素因子
}
for(int j=0; j<cnt; j++)
if(Vis[prime[j]])
add(n+Vis[prime[j]],n+Cnt+2,1,0); //素因子到汇点
mincost_maxflow(0,n+Cnt+2,n);
}
return 0;
}
H andy和购物
题意:水题,排序计算内积即可。
1 | while True: |
I andy种树
题意:每次选一个区间加一,然后最后想知道1-n每个坐标的数是多少。
分析:会线段树用线段树区间更新单点查询裸题。不会线段树用左家右减法即可,区间左端点加1,区间右端点再往右一个的位置减一,最后累加。烂大街的技巧。
1 | #include<bits/stdc++.h> |
J andy的树被砍了
题意:煞笔题还想好好伪装。
分析:伤害直接累加,然后求某棵树先加上对应前一个的累加伤害值,再在伤害数组中lower_bound()二分查找。
1 | #include<bits/stdc++.h> |