NOIP2017泛做

$\Omega$

嗯,这个代表“前言”的字母很帅。

先来总结一下每个题的难度,A题提高(证明)/普及-(找规律), B题提高, C题提高+,总结来看,Day1比较送;D题普及+,E题省选-,F题省选-,Day2不如Day1水。

PS: 提高以NOIP提高组平均难度为准,省选以弱省省选为准(比如以SNOI2019平均难度作为基准线)

$A$

·由于当时场上切了这道题,导致我对“找规律“这种投机取巧的做题方式情有独钟,从而在某些计数题时不好好想DP反而猜sb规律……感觉很GG……

其实这个题就是给一个方程:
$$
ax+by \not= t \quad x,y, \in\mathbb{N},\quad t\in \mathbb{N+} \quad (a,b)= 1
$$
求$\max{t}$

呃,首先,我想了一种很zz的证明方式:

  • 当$t = a \cdot b - a - b$时,$t$满足这个方程

    • 我们通过移项可以得到:

    • $$
      ax+by-ab+a+b=0 \\
      a(x-b +1) + b(y+1) = 0 \\
      $$

    • 观察这个式子,要么有$y+1=0$且$x-b+1=0$,要么有$a(b-x-1) = b(y+1)\cdots(1)$ . 第一种情况显然不成立,那么我们考虑第二种情况。此时因为$(a,b)=1$,所以会有$b~|~(b-x-1) \to b ~|~(x+1)$, 同理$a~|~(y+1)$ .但同时我们将$(1)$式搞一搞就可以得到$$\frac{a}{b} = \frac{b-(x+1)}{y+1}$$. 但因为$a,b \in \mathbb{N+}$,所以会有$b>(x+1)$ ; 因为$b~|~(x+1)$,有$b\leq x+1$或$x+1=0$(舍) ,矛盾,故此时$t$满足这个方程。

  • 当$t>a\cdot b-a-b$时,$t$总不满足。

    • 不妨设$t_0=a\cdot b-a-b, ~t=t_0+k, ~k\in\mathbb{N+}$
    • 此时……然后就不会了2333——以下是借鉴的星星之火OIer巨佬的思路:
  • 对于任意正整数$k\geq ab−a−b+1$,即$k+a+b\geq ab+1$

    • 设$k+a+b = \mu a+m~~(k\geq b,1\leq m <a)$. 同时:
      $$
      \because (a,b)=1\\
      \therefore \exists x_0,y_0 \in \mathbb{Z} \quad s.t. \quad ax_0+by_0=1 \\
      \therefore \exists x_1,y_1∈\mathbb{Z},−(b−1)\leq x_1\leq 0 \quad s.t.\quad ax_1+by_1=m\\
      $$
      这里的意思其实是设$−(b−1)\leq x_1\leq 0$,一定存在整数$y_1$使得$ax_1+by+_1=m$成立。原因就是在整数$x_1$的取值中一共有$b$个数,$y_1=(m−ax_1)/b$,根据鸽笼原理之类的zz定理,我们总是可以找到$x_1$使得$m−ax_1$能被$b$整除。

    显然,$y_1\geq 1(ax_1\leq 0,m >0, b>0, 因此y_1\geq 1,)$

    于是,取$x=\mu+x_1−1,y=y_1−1$

    注意到$x_1,y_1$的取值范围,得$x,y\geq 0$, 即有$ax+by=k$


???不知不觉写了小半个下午??看起来A题确实是结论题了(sigh

1
2
3
4
5
long long  A, B ;
int main(){
cin >> A >> B ;
cout << A * B - A - B ;
}

$B$

……像这种题不就是看脸题吗…手一抖就调不出来了$\rm{qaq}$

题解以前写过,于是直接把主要部分引用过来(以前的码风还真是抽搐

读入

我们先用$while$按字符读入每个程序的第一行,抠出需要检验的复杂度,$O(1)$用$0$来存$[n^0=1 $ $~~~$ $ (n!=0)]$.

注意,有可能有两位数,需要多扣一位……

1
2
3
4
5
6
7
8
9
10
11
12
13
>	  while(o!=')'){
> if(o=='1'&&!chk)
> need_check=0;
> if(o=='n'){
> cin>>o>>o;
> need_check=o-48;
> chk=1;
> }
> o=getchar();
> if(isdigit(o)&&chk)need_check*=10,need_check+=(o-48);
> }
> getchar();
>

至于最后为什么要再$gatchar()$一次……自己试试就知道了。

那么接下来就要按行读入循环了,比较简单。

初始化

为了使码风简洁,所以写到函数里了。这个地方我用到了三个栈,一个用来记录每个循环的答案(因为有可能有多个相互独立的循环),一个用来记录每次$F$时读入的循环上下界。以上两个都是$int$栈,还有一个$char$栈,存储每次定义的循环变量,而这个字符栈搭配一个$bool$性的数组,用于记录是否可用。

1
2
3
4
5
6
7
8
9
10
11
>#define MAX 1000000
>int i,x,y,t,tt,num,cntf,cnte,res,ans[MAX],T,l,now,need_checks,stk[MAX];
>bool check[150],flag,spj,chk;
>char s[3010],o,stkk[MAX];
>inline void init(){
> memset(check,0,sizeof(check));
>memset(stkk,0,sizeof(stkk));
>memset(stk,0,sizeof(stk));
>now=t=tt=cntf=cnte=res=flag=spj=chk=0;
>}
>

$ps:$虽然不知道用一个二进制位的$0$来初始化字符数组会怎样……不过好像海星。

$cnte$和$cntf$用来记录$F$和$E$的数量,$num$、$t$、$tt$都是栈的指针,$spj$用来判断一个独立循环是否结束(如果结束就把当前的得到压入栈),$now$用来搭配$spj$记录当前独立循环体的时间复杂度, $chk$用于读入每个程序的第一行(即含有需要判断的时间复杂度的那一行),$flag$用于判断输出。

主要操作

对于读入的东西,分类讨论,然后$continue$……没什么可说的。

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
>	   while(l--){
> gets(s);
> for(i=0;i<strlen(s);){
> while(s[i]==' ')i++;
> if(s[i]=='F'){
> if(cntf>cnte&&cnte){
> ans[++num]=now;
> now=0;
> }
> cntf++,i++;
> continue;
> }
> if(s[i]=='E'){
> y=stk[t],t--;
> x=stk[t],t--;
> cnte++;
> if(cnte==cntf)spj=1;
> if(x!=MAX){
> if(y==MAX)now++;
> if(y<x)now=0;
> }
> else{
> if(y!=MAX)now=0;
> }
> check[stkk[tt]-'a']=0;
> tt--,i++;
> if(spj){
> ans[++num]=now;
> now=0;
> spj=0;
> }
> continue;
> }
> if(!isdigit(s[i])&&s[i]!='n'){
> if(check[s[i]-'a']&&!flag){
> cout<<"ERR"<<endl;
> flag=1;
> }
> stkk[++tt]=s[i];
> check[s[i]-'a']=1;
> }
> else {
> if(s[i]=='n'){
> my_push(s[i],s[i+1]);
> i+=2;
> }
> my_push(s[i],s[i+1]);
> }
> i++;
> }
> }
>

唯一需要注意的是入栈操作,因为要把字符压入整型,所以我又写了个函数来入栈。入栈的时候当然需要注意是不是两位数……

哦,还有,如果这次轮到$n$入栈了,那么就随便入栈一个大于一百的数即可。

1
2
3
4
5
6
7
8
9
10
11
>inline void my_push(char a,char b){
> if(isdigit(a)){
> if(isdigit(b)){
> stk[++t]=(a-48)*10+b-48;
> i++;
> }
> else stk[++t]=a-48;
> }
> if(a=='n')stk[++t]=MAX;
>}
>

最后判断一下输入输出即可

1
2
3
4
5
6
7
8
9
10
11
>	   if(!flag&&cntf!=cnte){
> cout<<"ERR"<<endl;
> flag=1;
> }
> while(num){
> res=max(res,ans[num]);
> num--;
> }
> if(!flag) if(res==need_check) cout<<"Yes"<<endl;
> else cout<<"No"<<endl;
>

嗯~o( ̄▽ ̄)o这就是满分做法了。

唉,时光一去不复返啊。

$C$

……其实不算是个新题,只是似乎当时这道题场上很卡常?感觉就是好多东西的杂糅,先SPFA判个全$0$环,再倒着记搜一遍……感觉已经不算什么新题了,T3出成这样感觉很失望qaq……

但怎么说呢,也是个练习码力的机会吧,转移方程挺好想的。

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
deque <int> q ;  
bitset <MAXN> vis ;
struct Edge{
int fr, to, next, v ;
}E[MAXM] ; int head[MAXN][2], cnt ;
int T, N, L, M, K, P, A, B, C, ss[MAXN] ;
int Es[MAXM][2], dfn[MAXN], low[MAXN], tot ;
bool flag ; LL Ans, dp[MAXN][MAXK], dist[MAXN] ;

inline void _Add(int u, int v, int w){
E[++ cnt].to = v, E[cnt].v = w, E[cnt].next = head[u][1], head[u][1] = cnt ;
E[++ cnt].to = u, E[cnt].v = w, E[cnt].next = head[v][0], head[v][0] = cnt ;
}
inline void Init(){
register int k ;
vis.reset() ;
memset(dp, -63, sizeof(dp)), cnt = 0 ;
for (k = 0 ; k <= L + 3 ; ++ k)
dist[k] = Inf, ss[k] = head[k][1] = head[k][0] = 0 ;
}
inline void SPFA(){
register int now, k ;
q.push_front(1), vis[1] = 1, dist[1] = 0, ++ ss[1] ;
while (!q.empty()){
now = q.front(), vis[now] = 0, q.pop_front() ;
for (k = head[now][1] ; k ; k = E[k].next){
if (dist[to(k)] >= dist[now] + E[k].v){
++ ss[to(k)] ;
dist[to(k)] = dist[now] + E[k].v ;
if (ss[to(k)] >= N){ flag = 1 ; return ; }
if (!vis[to(k)]){
if (q.empty() || dist[to(k)] < dist[q.front()])
q.push_front(to(k)) ; else q.push_back(to(k)) ; vis[to(k)] = 1 ;
}
}
}
}
}
LL dp_work(int now, int op){
if (dp[now][op] >= 0) return dp[now][op] ; dp[now][op] = 0 ;
for (register int k = head[now][0] ; k ; k = E[k].next){
LL t = op - dist[to(k)] + dist[now] - E[k].v ;
if (t > K || t < 0) continue ; dp[now][op] = (dp[now][op] + dp_work(to(k), t)) % P ;
}
return dp[now][op] ;
}
int main(){
register int i ; cin >> T ;
while(T --){
L = 200000, Init() ; Ans = 0 ;
N = qr(), M = qr(), K = qr(), P = qr() ;
for (i = 1 ; i <= M ; ++ i) A = qr(), B = qr(), C = qr(), _Add(A, B, C) ;
SPFA() ; dp[1][0] = 1 ; L = N ; if (flag) { flag = 0, printf("-1\n") ; continue ; }
for (i = 0 ; i <= K ; ++ i) Ans = (Ans + dp_work(N, i)) % P ; printf("%lld\n", Ans) ;
}
return 0 ;
}

想了一下,似乎出题人是故意把时间押给$B$的,所以$C$比较送。

$D$

也是挺送的一道题,注意开long long就好…用并查集维护一下最上面和最下面的两个洞在不在一条“连通链”上即可。

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
struct hole{
long long x,y,z;
}c[10001];
inline long long find(long long a)
{
if(f[a]!=a)a=find(f[a]);
return a;
}
inline void unionn(long long xz,long long yz)
{
if(c[find(yz)].z>c[find(xz)].z) f[find(yz)]=f[find(xz)];
else f[find(xz)]=f[find(yz)];
}
inline bool check(hole a,hole b)z
{
long long d;
d=(a.z-b.z)*(a.z-b.z)+(a.y-b.y)*(a.y-b.y)+(a.x-b.x)*(a.x-b.x);
if(d<=4*r*r)return 1;
return 0;
}
int main()
{
cin>>t;
while(t--)
{
memset(f,0,sizeof(0));
cin>>n>>h>>r;
for(long long i=1;i<=n;i++)
{
scanf("%lld%lld%lld",&c[i].x,&c[i].y,&c[i].z);
f[i]=i;
}
for(long long i=1;i<=n;i++)
for(long long j=i+1;j<=n;j++)
if(f[i]!=f[j]&&check(c[i],c[j]))unionn(i,j);
bool cc=0;
for(long long i=1;i<=n;i++)
if(c[i].z+r>=h&&c[find(i)].z-r<=0)
{
cc=1;
cout<<"Yes"<<endl;
break;
}
if(!cc)cout<<"No"<<endl;
cc=0;
}
return 0;
}

wtm以前的码风是有多犀利啊,字符间不加空格大括号也不换行

$E$

emmm第一眼状压,第二眼需要把树高加到状态里,那么就是$f_{s,h}$表示现在选的点集为$S$,树高为$h$的最小花费。转移的时候大概就是朴素的
$$
f_{s,i} = \min\limits {t \in s}{f{t,i-1}+cost_{t\to s}}
$$

然后这个cost显然是可以在可接受的复杂度以内$prework$出来的。于是最终的复杂度就是$\Theta(3^n\cdot n^2)$

求“子集的子集”的复杂度严格来讲是$3^n$而不是$4^n$,原因在于我们事实上一共有$\sum \binom{n}{k}2^k$个子集,逆向二项式展开或者叫二项式收缩一下就可以得到$$\sum \binom{n}{k}2^k = \sum \binom{n}{k}1^{n-k}\cdot 2^k = (1+2)^n = 3^n$$代码实现:

1
2
> for(t = S ; t ; t = (t - 1) & S)
>

呃,至于这句话的原理暂不可知,但是挺好用是真的qwq

但是复杂度上限此时是$531441\times 12^2= 76527504$,不可过(但事实上根本不可能跑满所以也过了),以下是Flash_hu巨佬的$\Theta(3^nn)$的做法:

我们发现似乎同一树高的所有节点,完全可以同时转移。所以我们不妨设$f_{s,t}$表示已选点集为$s$,下一层要加入的点集为$t$时, 新加入的所有点与原有点之间最小的边权之和——用于预处理。 具体的转移我们可以考虑如下:

$$
f_{s,t} = \min {f_{s,t-lowbit(j)}+cost_{k, s}}, k=\log 2lowbit(j)
$$
其中$cost
{k,s}$表示点$k$到连通块$s$的最短距离。可以用$lowbit$的原因是答案无序,所以这一部分的复杂度是$O(3^nn).$

那么接下来考虑原先的$dp$,设$g_{s,h}$表示已选点集为$s$,当前树高为$h$的最小代价,即目标函数。那么转移就是:
$$
g_{s,h} = \sum_{t\in s}g_{s-t, h-1}+h\cdot f_{s-t,t}
$$
同样是显然的。所以最后的复杂度就是$O(3^nn)$ 。答案的话最后直接对所有$g_{_{2^n-1,h}},h\in[1,n]$取个最小值就好了。

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
int cnt, T, D[MAX][MAX], a, b, c ;
int F[MAXN][MAX], Next[MAX], Ans, Sup, Now ;
int N, M, i, j, k, Log[MAX], Max, A[MAXN][MAXN] ;

int main(){
memset(A, 63, sizeof(A)) ;
memset(F, 63, sizeof(F)), Ans = Inf ;
cin >> N >> M ; Max = (1 << N) - 1 ;
for (i = 1 ; i <= M ; ++ i)
scanf("%d%d%d", &a, &b, &c),
A[a][b] = A[b][a] = min(c, A[a][b]) ;
for (i = 0 ; i <= N ; ++ i) Log[1 << i] = i ;
for (i = 0 ; i <= N ; ++ i) F[0][1 << i] = 0 ;
for (i = 1 ; i <= Max ; ++ i){
cnt = 0 ;
for (j = Sup = Max ^ i; j ; j = (j - 1) & Sup) Next[j] = cnt, cnt = j ;
for (j = cnt ; j ; j = Next[j]){
Now = Log[j & (-j)] + 1, T = Inf ;
for (k = 1; k <= N ; ++ k)
if (1 << (k - 1) & i) T = min(T, A[Now][k]) ;
D[i][j] = D[i][j ^ (j & -j)] + T ;
}
}
for (i = 1 ; i < N ; ++ i)
for (j = 1 ; j <= Max; ++ j)
for (k = j ; k ; k = (k - 1) & j)
F[i][j] = min(F[i][j], F[i - 1][j ^ k] + i * D[j ^ k][k]) ;
for (i = 0 ; i <= N ; ++ i) Ans = min(Ans, F[i][Max]) ;
cout << Ans << endl ; return 0 ;
}

$F$

一道我不是很会的线段树题……

怎么说呢,感觉这个做法未曾见过吧。大概就是维护$n+1$棵动态开点的线段树,其中对每一行的前$m-1$个元素维护一个线段树,然后对最后一列单独维护一棵线段树。线段树上每个点维护自己子树内到底有多少个点被删了,用来协助寻找现在的位置。在此基础上再维护$n+1$个vector,用来记录从每棵线段树中弹出的点即可。

呃,现在的我似乎并没有很好地理解这个题的做法,有些马虎…所以希望日后再看的时候能看的更清明一点吧。

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
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>

int N, M, Q ;
using namespace std ;

inline int qr(){
register int k = 0 ; char c = getchar() ; while(!isdigit(c)) c = getchar() ;
while(isdigit(c)) k = (k << 1) + (k << 3) + c - 48, c = getchar() ; return k ;
}

namespace vio{
#define MAXV 2010
int x, y, t, i, j ;
int base[MAXV][MAXV] ;
void Solve1(){
t = 0 ;
for (i = 1 ; i <= N ; ++ i)
for (j = 1 ; j <= M ; ++ j)
base[i][j] = ++ t ;
while(Q --){
x = qr(), y = qr(), t = base[x][y] ;
for (i = y + 1 ; i <= M ; ++ i) base[x][i - 1] = base[x][i] ;
for (i = x + 1 ; i <= N ; ++ i) base[i - 1][M] = base[i][M] ;
printf("%d\n", (base[N][M] = t)) ;
}
}
}
namespace segment_T{
#define MAXN 400010
#define ll long long
#define pb push_back
#define rr register int
vector<ll> del[MAXN << 4] ; int Max ;
int rt[MAXN << 4], L[MAXN << 4], R[MAXN << 4], dfn, val[MAXN << 4] ;
inline void update(int &root, int l, int r, int pos){
if (!root) root = ++ dfn ; val[root] ++ ; if (l == r) return ; rr mid = (l + r) >> 1 ;
if (pos <= mid) update(L[root], l, mid, pos) ; else update(R[root], mid + 1, r, pos) ;
}
inline int query(int root, int l, int r, int pos){
if (l == r) return l ; rr mid = (l + r) >> 1, dif = mid - l + 1 - val[L[root]] ;
if (dif >= pos) return query(L[root], l, mid, pos) ; else return query(R[root], mid + 1, r, pos - dif) ;
}
inline ll delcase2(int x, ll y){
rr now_p = query(rt[N + 1], 1, Max, x) ; update(rt[N + 1], 1, Max, now_p) ;
ll ret = now_p <= N ? 1LL * now_p * M : del[N + 1][now_p - N - 1] ; del[N + 1].pb(y ? y : ret) ; return ret ;
}
inline ll delcase1(int x, int y){
rr now_p = query(rt[x], 1, Max, y) ; update(rt[x], 1, Max, now_p) ;
ll ret = now_p < M ? 1LL * (x - 1) * M + now_p : del[x][now_p - M] ; del[x].pb(delcase2(x, ret)) ; return ret ;
}
inline void Solve2(){
rr x, y ; Max = max(N, M) + Q ;
while (Q --) x = qr(), y = qr(), printf("%lld\n", y != M ? delcase1(x, y) : delcase2(x, 0)) ;
}
}
int main(){
cin >> N >> M >> Q ;
if (N <= 5000 && M <= 5000) vio :: Solve1() ;
else segment_T :: Solve2() ;/*pkspkspks*/ return 0 ;
}

$\varPhi$

现在来看,乐观估计,自己应该可以得到$100+100+100+100+55+30=485pts$,当且仅当自己的码力已经很强。如果是悲观估计,那大概是$100+70+40+80+55+30=375pts$。继续努力吧,现在还差得很远啊……