前言
昨天又修到好晚…早上起来跟死人差不多
然后今天上来发现T1T2T3都没思路,于是我选择放弃T2T3肛T1,然后我就和一个没学过的算法斗了两个多小时…彻底凉凉.
后面发现T2是个思博DP,当时就感觉不爽了…又被一个初中学弟真 $\cdot$ 嘲讽了…更不爽了(* ￣︿￣)
菜果然是原罪
今天题质量还行,比较接近NOIP,我还考这鬼样
T1 phalanx
你会二分图匹配的话就是水题了,直接转化成最大独立集就好了
考试的时候千万不要把时间浪费在你的瞎搞做法上
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
| struct Edge{
int ne,to;
}edge[maxn<<2];
int h[maxn<<1],num_edge=1;
inline void add_edge(int f,int to){
edge[++num_edge].ne=h[f];
edge[num_edge].to=to;
h[f]=num_edge;
}
int match[maxn<<1],pre[maxn<<1];
int vis[maxn<<1];
int n,num;
inline void solve(){
int u,v,s,t,tmp,ans=0;
bool flag=0;
queue <int> q;
for(ri i=1;i<=n*2;i++)vis[i]=0,match[i]=pre[i]=-1;
for(ri o=1;o<=n;o++){
if(match[o]==-1){
while(q.size())q.pop();
q.push(o);
pre[o]=-1,flag=0;
while(q.size()&&!flag){
u=q.front();q.pop();
for(ri i=h[u];i&&!flag;i=edge[i].ne){
v=edge[i].to;
if(vis[v]==o)continue;
vis[v]=o;
if(match[v]!=-1){
q.push(match[v]);
pre[match[v]]=u;
}
else{
flag=1;
s=u,t=v;
while(s!=-1){
tmp=match[s];
match[s]=t,match[t]=s;
t=tmp,s=pre[s];
}
}
}
}
}
if(match[o]!=-1)ans++;
}
printf("%d\n",(n*2-ans)*n);
}
int main(){
int x,y;
freopen("phalanx.in","r",stdin);
freopen("phalanx.out","w",stdout);
read(n),read(num);
for(ri i=1;i<=num;i++){
read(x),read(y);
add_edge(x,y+n);
add_edge(y+n,x);
}
solve();
return 0;
}
|
T2 math
运算就是(a+b)/2,考试时没怎么仔细想,其实就是道套路区间DP,我们枚举合并的中断点就好了,使用位运算判断
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
| const int maxn=155;
const int inf=0x7fffffff;
int f[maxn][maxn],n,a[maxn];
int o[259][259],px[8],py[8];
int main(){
int x,y;
freopen("math.in","r",stdin);
freopen("math.out","w",stdout);
read(n);
for(ri i=1;i<=n;i++)read(a[i]);
if(n==1){printf("%d\n",a[1]);return 0;}
if(n==2){printf("%d\n",(a[1]+a[2])/2);return 0;}
for(ri i=1;i<=n;i++)f[i][i]=(1<<a[i]);
for(ri len=2;len<=n;len++){
for(ri l=1,r;l<=n-len+1;l++){
r=l+len-1;
for(ri k=l;k<r;k++){
for(ri p=0;p<8;p++)if(f[l][k]&(1<<p)){
for(ri q=0;q<8;q++)if(f[k+1][r]&(1<<q)){
f[l][r]|=(1<<((p+q)>>1));
}
}
}
}
}
for(ri i=0;i<8;i++)if(f[1][n]&(1<<i))printf("%d ",i);
return 0;
|
还可以预处理两个数能合并成哪个状态
同时如果结果一定是连续的话可以用这篇博客中的方法:https://www.cnblogs.com/charlotte-Y/p/9873039.html
orz 高一人赢WYT
T3 park
有个暴力的$O(NQ)$做法可以得85分,我们记录最大值判断一下就可以了,卡时可以多得10分
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
| const int maxn=40005;
const int inf=0x7fffffff;
int n,q;
int d[maxn],lim[maxn];
namespace bf{
int l,r,ind,sum,ans=0,pos,anss=-1;
void main(){
while(q--){
read(l),read(r),read(ind);
if(anss!=-1){
printf("%d\n",anss);
continue;
}
ans=ind,pos=l,sum=ind;
for(ri i=l;i<=r;i++){
sum= (sum+d[i]>lim[i]) ? lim[i] : sum+d[i];
if(sum<ind)sum=ind;
else ans=max(ans,sum);
}
printf("%d\n",ans);
if(clock()>CLOCKS_PER_SEC*1.8)anss=ans;
}
return ;
}
}
int main(){
freopen("park.in","r",stdin);
freopen("park.out","w",stdout);
read(n),read(q);
for(ri i=1;i<=n;i++)read(d[i]);
for(ri i=1;i<=n;i++)read(lim[i]);
bf::main();
return 0;
}
|
…
不管怎样这次考试也算是个警醒吧,心态也没有太崩,不能再颓了(Flag)
一首摇滚,来自CSGO音乐盒,这个把Life Is Not Out To Get You翻译成”人生何处不青山”,一下子就感觉逼格上去了,服气,虽然不太理解为什么这么译