从此加入快读大军乐
1
2
3
4
5
6
| inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch == '-') f=-1 ; ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48) ; ch=getchar();}
return x*f;
}
|
T1 对抗赛
首先考虑在什么情况下无解
显然是没法平均分的情况下
因此，如果这些奖品的总价值 $\text{sum}$ 为奇数，可以直接输出 $0$
接下来就是找凑成 $\dfrac{\text{sum}}{2}$ 的方案数了
设 $f(i)$ 表示凑成 $i$ 的方案数，$A_j$ 表示物品 $j$ 的价值，注意逆序枚举
那么状态转移方程为 $f(i) = \displaystyle \sum^{j\leq\text{sum}/2}_{j=A_j}f(i-A_j)$
初始状态：$f(0)=1$
1
2
3
4
5
6
7
| dp[0] = 1;
for(int i = 1;i<=N;i++){
for(int j = HS;j>=A[i];j--){
dp[j] += dp[j - A[i]];
}
}
printf("%d",dp[HS]>>1);
|
T2 热浪
直接套 $\operatorname{Dijkstra}$ 板子就行
T3 演讲大厅安排
挺像贪心的dp
之前好像做过类似的题但我找不到了（
首先按照结束时间排序
然后对于每个事件，找出在它之前最多可以进行总演讲时长
然后加上本场演讲的时长
1
2
3
4
5
6
7
| sort(event+1,event+N+1);
for(int i = 1;i<=N;i++){
for(int j = 1;j<i;j++){
if(event[i].st >= event[j].ed) dp[i] = max(dp[i],dp[j]);
}
dp[i] += event[i].len;
}
|
T4 分糖果
被极限数据卡自闭了
十万个小朋友是什么概念
其实也是 $\operatorname{Dijkstra}$ 板子题
但是数据有点过分
用了快读、堆优化 $\operatorname{Dijkstra}$ 、邻接表存图才卡着时限过的点
（我也不知道为什么邻接表能过链式前向星过不了
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;
#define FO(name) freopen(name".in","r",stdin);freopen(name".out","w",stdout)
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch == '-') f=-1 ; ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48) ; ch=getchar();}
return x*f;
}
const int maxN = (1e5+10);
vector<int>edge[maxN];
int dis[maxN];
int vis[maxN];
int ans;
struct Node{
int dis,pos;
friend bool operator < (Node A,Node B){
return A.dis > B.dis;
}
};
inline void Dijkstra(int s){
memset(dis,0x7f,sizeof(dis));
priority_queue<Node> Q;
dis[s] = 1;
vis[s] = 1;
Q.push((Node){1,s});
while(!Q.empty()){
int u = Q.top().pos;
Q.pop();
for(register int i = 0;i<edge[u].size();i++){
int v = edge[u][i];
if(dis[v] > dis[u] + 1){
dis[v] = 1 + dis[u];
if(!vis[v]){
Q.push((Node){dis[v],v});
vis[v] = 1;
ans = max(ans,dis[v]);
}
}
}
}
}
int N,P,C;
int M;
int main(){
FO("candy");
N=read(),P=read(),C=read(),M=read();
for(register int i = 1;i<=P;i++){
int a,b;
a = read();
b = read();
edge[a].push_back(b);
edge[b].push_back(a);
}
Dijkstra(C);
printf("%d\n",ans+M);
return 0;
}
|