NOIP 模擬賽 8
NOIP 模擬賽總結
NOIP 模擬賽 8
嗚嗚嗚，直接叫(jiao) T1 模擬(ni)賽吧。
T1 王哥與荷塘（fish）
發現要求的是曼哈頓距離的最遠點對。
根據(ju) HZ戰(zhan)神(shen) 王戰(zhan)普老(lao)師的教導(dao)可知。
任意兩點(dian)的(de)曼哈頓(dun)距離(li)可以通(tong)過(guo)橫縱坐標和與差求出(chu)。
所以問題轉(zhuan)化為維(wei)護每個點(dian)橫(heng)縱坐標和與差的最值(zhi)。
我是直接上分塊(kuai)維護了。
賽時想成了還(huan)要(yao)維護下標，所以調(diao)了一整場的(de)大分(fen)塊qwq。
唐完了，不想評價。
點擊查看代碼
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <cmath>
#define int long long
#define con putchar_unlocked(' ')
#define ent putchar_unlocked('\n')
#define Blue_Archive return 0
using namespace std;
constexpr int N = 2e5 + 3;
constexpr int M = 450;
constexpr int INF = 1e9;
int n;
int m;
int len;
int L[M];
int R[M];
int id[N];
int laz[M];
struct mika
{
int amx,amxid;
int amn,amnid;
int bmx,bmxid;
int bmn,bmnid;
}b[M];
struct miku
{
int x,y; // x + y{max} -> x{min} x + y{min} -> x{max}
}a[N];
inline int read() // 不讀負數的普通快讀
{
int k = 0,f = 1;
int c = getchar_unlocked();
while(c < '0' || c > '9') c = getchar_unlocked();
while(c >= '0' && c <= '9') k = (k << 3) + (k << 1) + (c ^ 48),c = getchar_unlocked();
return k * f;
}
inline void write(int x) // 普通快寫
{
if(x < 0) putchar_unlocked('-'),x = -x;
if(x > 9) write(x / 10);
putchar_unlocked(x % 10 + '0');
}
inline void work_laz(int id)
{
laz[id] %= 4;
for(int i = 1;i <= laz[id];i ++)
{
for(int j = L[id];j <= R[id];j ++)
{
swap(a[j].x,a[j].y);
a[j].x = -a[j].x;
}
}
laz[id] = 0;
}
inline void work(int l,int r,mika&res)
{
for(int i = l,h,c;i <= r;i ++)
{
h = a[i].x + a[i].y;
c = a[i].y - a[i].x;
if(h > res.amx) res.amx = h,res.amnid = a[i].x;
if(h == res.amx && res.amnid > a[i].x) res.amnid = a[i].x;
if(h < res.amn) res.amn = h,res.amxid = a[i].x;
if(h == res.amn && res.amxid < a[i].x) res.amxid = a[i].x;
if(c > res.bmx) res.bmx = c,res.bmnid = a[i].y;
if(c == res.bmx && res.bmnid > a[i].y) res.bmnid = a[i].y;
if(c < res.bmn) res.bmn = c,res.bmxid = a[i].y;
if(c == res.bmn && res.bmxid < a[i].y) res.bmxid = a[i].y;
}
}
inline void change(int l,int r)
{
if(id[l] == id[r])
{
if(laz[id[l]]) work_laz(id[l]);
for(int i = l,op;i <= r;i ++)
{
swap(a[i].x,a[i].y);
a[i].x = -a[i].x;
}
b[id[l]] = {-INF,-INF,INF,INF,-INF,-INF,INF,INF};
work(L[id[l]],R[id[l]],b[id[l]]);
return;
}
if(laz[id[l]]) work_laz(id[l]);
for(int i = l;i <= R[id[l]];i ++)
{
swap(a[i].x,a[i].y);
a[i].x = -a[i].x;
}
b[id[l]] = {-INF,-INF,INF,INF,-INF,-INF,INF,INF};
work(L[id[l]],R[id[l]],b[id[l]]);
if(laz[id[r]]) work_laz(id[r]);
for(int i = L[id[r]];i <= r;i ++)
{
swap(a[i].x,a[i].y);
a[i].x = -a[i].x;
}
b[id[r]] = {-INF,-INF,INF,INF,-INF,-INF,INF,INF};
work(L[id[r]],R[id[r]],b[id[r]]);
for(int i = id[l] + 1;i < id[r];i ++)
{
mika op = b[i];
b[i] = {-op.bmn,-op.bmnid,-op.bmx,-op.bmxid,op.amx,op.amxid,op.amn,op.amnid};
laz[i] ++;
laz[i] %= 4;
}
}
inline int query(int l,int r)
{
int ans = 0;
mika res = {-INF,-INF,INF,INF,-INF,-INF,INF,INF};
if(id[l] == id[r])
{
if(laz[id[l]]) work_laz(id[l]);
work(l,r,res);
ans = max(ans,res.amx - res.amn + ((res.amxid > res.amnid) ? 2 * (res.amxid - res.amnid) : 0));
ans = max(ans,res.bmx - res.bmn + ((res.bmxid > res.bmnid) ? 2 * (res.bmxid - res.bmnid) : 0));
return ans;
}
if(laz[id[l]]) work_laz(id[l]);
work(l,R[id[l]],res);
if(laz[id[r]]) work_laz(id[r]);
work(L[id[r]],r,res);
for(int i = id[l] + 1;i < id[r];i ++)
{
if(b[i].amx > res.amx) res.amx = b[i].amx,res.amnid = b[i].amnid;
if(b[i].amx == res.amx && res.amnid > b[i].amnid) res.amnid = b[i].amnid;
if(b[i].amn < res.amn) res.amn = b[i].amn,res.amxid = b[i].amxid;
if(b[i].amn == res.amn && res.amxid < b[i].amxid) res.amxid = b[i].amxid;
if(b[i].bmx > res.bmx) res.bmx = b[i].bmx,res.bmnid = b[i].bmnid;
if(b[i].bmx == res.bmx && res.bmnid > b[i].bmnid) res.bmnid = b[i].bmnid;
if(b[i].bmn < res.bmn) res.bmn = b[i].bmn,res.bmxid = b[i].bmxid;
if(b[i].bmn == res.bmn && res.bmxid < b[i].bmxid) res.bmxid = b[i].bmxid;
}
ans = max(ans,res.amx - res.amn + ((res.amxid > res.amnid) ? 2 * (res.amxid - res.amnid) : 0));
ans = max(ans,res.bmx - res.bmn + ((res.bmxid > res.bmnid) ? 2 * (res.bmxid - res.bmnid) : 0));
return ans;
}
signed main()
{
freopen("fish.in","r",stdin);freopen("fish.out","w",stdout);
// freopen("data.in","r",stdin);freopen("data.out","w",stdout);
n = read();
m = read();
len = sqrt(n);
for(int i = 1,h,c;i <= n;i ++)
{
a[i].x = read();
a[i].y = read();
id[i] = (i - 1) / len + 1;
if(!L[id[i]]) L[id[i]] = i;
R[id[i]] = i;
}
for(int i = 1;i <= id[n];i ++)
{
b[i] = {-INF,-INF,INF,INF,-INF,-INF,INF,INF};
work(L[i],R[i],b[i]);
}
for(int i = 1,op,l,r;i <= m;i ++)
{
op = read();
l = read();
r = read();
if(op == 1) // change
{
change(l,r);
}
if(op == 2) // query
{
write(query(l,r)),ent;
}
}
Blue_Archive;
}
T2 王哥與演出（oblivious）
話說這題我講的欸
考慮(lv)每個(ge)橫縱(zong)坐標(biao)頂多與一件物(wu)品對(dui)應。
貪心地將物品按權值排序，考慮(lv)還能不能被選(xuan)即可。
點擊查看代碼
#include <bits/stdc++.h>
#define int long long
#define con putchar_unlocked(' ')
#define ent putchar_unlocked('\n')
#define Blue_Archive return 0
using namespace std;
constexpr int N = 1e6 + 3;
constexpr int M = 450;
constexpr int INF = 1e9;
int n;
int m;
int K;
int ans;
int fa[N << 1];
int siz[N << 1];
struct miku
{
int x,y,val;
}a[N];
inline int read() // 不讀負數的普通快讀
{
int k = 0,f = 1;
int c = getchar_unlocked();
while(c < '0' || c > '9') c = getchar_unlocked();
while(c >= '0' && c <= '9') k = (k << 3) + (k << 1) + (c ^ 48),c = getchar_unlocked();
return k * f;
}
inline void write(int x) // 普通快寫
{
if(x < 0) putchar_unlocked('-'),x = -x;
if(x > 9) write(x / 10);
putchar_unlocked(x % 10 + '0');
}
inline int find(int x){return x == fa[x] ? x : fa[x] = find(fa[x]);}
signed main()
{
freopen("oblivious.in","r",stdin);freopen("oblivious.out","w",stdout);
// freopen("data.in","r",stdin);freopen("data.out","w",stdout);
K = read();
n = read();
m = read();
for(int i = 1;i <= K;i ++)
{
a[i].x = read();
a[i].y = read() + n;
a[i].val = read();
}
sort(a + 1,a + K + 1,[](miku a,miku b){return a.val > b.val;});
for(int i = 1;i <= n + m;i ++) fa[i] = i,siz[i] = 1;
for(int i = 1,p,q;i <= K;i ++)
{
p = find(a[i].x);
q = find(a[i].y);
if(p == q)
{
if(!siz[p]) continue; // 不選 ta
siz[p] --;
ans += a[i].val;
}
else
{
if(!siz[p] && !siz[q]) continue; // 不選 ta
fa[p] = q;
siz[q] += siz[p] - 1;
ans += a[i].val;
}
}
write(ans);ent;
Blue_Archive;
}
T3：王哥與序列（array）
困難題。
首(shou)先(xian)直接考慮在差分序列上操作。
這樣操作就轉化成對任意兩點分別 \(+x\) or \(-x\)。或單點任意修改。
考慮一個 \(dp_S\)。
表示集合 \(S\) 中的數均(jun)被(bei)處(chu)理(li)過的最小(xiao)操作(zuo)次數。
可以直接枚舉子集轉移 \(dp_S = min_{T \in S}{(dp_T + dp_{S \oplus T})}\)。
然后考慮計數。
發現如果只用操作一，其方案數為 \(siz^{siz - 2}\)，\(siz\) 為已(yi)處理集合(he)的大(da)小(xiao)。
如果加上操作二，則操作二會且僅會被執行一次（因為執行操作一嚴格優于操作二），其方案數為 \(2 * (siz + 2)^{i - 1}\)。
然后這個直接跟隨 \(dp\) 數組轉移即可。
時間復雜度是 \(O(3 ^ {n - 1})\)。
還要卡常qwq。
考慮如果初始差分數組為 \(0\) 的直(zhi)接跳過就行了。
Too Hard! QwQ
點擊查看代碼
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <cmath>
#include <bitset>
#define int long long
#define con putchar_unlocked(' ')
#define ent putchar_unlocked('\n')
#define Blue_Archive return 0
using namespace std;
constexpr int N = 25;
constexpr int INF = 1e9;
constexpr int mod = 1e9 + 7;
int n;
int top;
int ans1;
int ans2;
int a[N];
int b[N];
int c[N];
int fac[N];
int siz[1 << 22];
int g[1 << 22];
int dp[1 << 22];
bitset<1 << 22> op;
bitset<1 << 22> vis;
inline int read() // 讀負數的普通快讀
{
int k = 0,f = 1;
int c = getchar_unlocked();
while(c < '0' || c > '9') f = (c == '-') ? -1 : f,c = getchar_unlocked();
while(c >= '0' && c <= '9') k = (k << 3) + (k << 1) + (c ^ 48),c = getchar_unlocked();
return k * f;
}
inline void write(int x) // 普通快寫
{
if(x < 0) putchar_unlocked('-'),x = -x;
if(x > 9) write(x / 10);
putchar_unlocked(x % 10 + '0');
}
inline int qpow(int a,int b)
{
if(b < 0) return 0;
int res = 1;
while(b)
{
if(b & 1) res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
signed main()
{
freopen("array.in","r",stdin);freopen("array.out","w",stdout);
// freopen("data.in","r",stdin);freopen("data.out","w",stdout);
n = read();
for(int i = 1;i <= n;i ++) a[i] = read();
n --;
for(int i = 1;i <= n;i ++) if(a[i + 1] - a[i] != 0) b[++ top] = a[i + 1] - a[i];
n = top;
fac[0] = c[0] = 1;
for(int i = 1;i <= n + 1;i ++) c[i] = 2 * qpow(i + 2,i - 1) % mod;
for(int i = 1;i <= n;i ++) fac[i] = fac[i - 1] * i % mod;
for(int i = 1,sum;i < (1 << n);i ++)
{
sum = 0;
for(int j = 0;j < n;j ++) if(i & (1 << j)) sum += b[j + 1],siz[i] ++;
if(!sum)
{
dp[i] = 1;
if(siz[i] == 1) g[i] = 1;
else g[i] = qpow(siz[i],siz[i] - 2);
}
}
for(int i = 1,jk;i < (1 << n);i ++)
{
if(!dp[i]) continue;
jk = 1;
for(int j = (i - 1) & i;j;j = (j - 1) & i) if(dp[j]){jk = 0;break;}
op[i] = jk;
}
for(int i = 1;i < (1 << n);i ++)
{
if(!dp[i]) continue;
vis.reset();
for(int j = (i - 1) & i;j;j = (j - 1) & i)
{
if(op[j] && !vis[j])
{
if(dp[j] + dp[i ^ j] > dp[i]) dp[i] = dp[j] + dp[i ^ j],g[i] = g[j] * g[i ^ j] % mod;
else if(dp[j] + dp[i ^ j] == dp[i]) (g[i] += g[j] * g[i ^ j] % mod) %= mod;
for(int k = (i ^ j);k;k = (k - 1) & (i ^ j)) vis[k] = 1;
}
}
}
for(int i = 0;i < (1 << n);i ++) ans1 = max(ans1,dp[i]);
ans1 = n - ans1;
if(ans1 == n) ans2 = 2 * qpow(n + 2,n - 1) * fac[ans1] % mod;
else
{
for(int i = 0;i < (1 << n);i ++)
{
if(dp[i] == n - ans1)
{
ans2 = (ans2 + g[i] * c[n - siz[i]] % mod) % mod;
}
}
ans2 = ans2 * fac[ans1] % mod;
}
write(ans1);ent;
write(max(ans2,1ll));ent;
Blue_Archive;
}
有注釋版本qwq
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,cnt,ans1,ans2,a[23],b[23],c[23],fac[23],dp[1 << 22],g[1 << 22],vis[1 << 22],TAG[1 << 22],siz[1 << 22],mod = 1e9 + 7;
inline int read()
{
int s = 0,w = 1;
char ch = getchar();
while (ch < '0'|| ch > '9'){if(ch == '-') w = -1;ch = getchar();}
while (ch >= '0'&& ch <= '9') s = (s << 1) + (s << 3) + (ch ^ 48),ch = getchar();
return s * w;
}
int qpow(int x,int y)
{
if(y < 0) return 0;
int a = 1,b = x;
while(y)
{
if(y & 1) a = a * b % mod;
b = b * b % mod;
y >>= 1;
}
return a;
}
signed main()
{
freopen("array.in","r",stdin);freopen("array.out","w",stdout);
// freopen("data.in","r",stdin);freopen("ans.out","w",stdout);
n = read();
for(int i = 0;i < n;i ++) a[i] = read();
n --;
for(int i = 0;i < n;i ++) b[i] = a[i + 1] - a[i];
fac[0] = c[0] = 1;
for(int i = 1;i <= n + 1;i ++) c[i] = 2 * qpow(i + 2,i - 1) % mod;
for(int i = 1;i <= n;i ++) fac[i] = fac[i - 1] * i % mod;
for(int i = 1,sum;i < (1 << n);i ++)
{
sum = 0;
for(int j = 0;j < n;j ++) if(i & (1 << j)) sum += b[j],siz[i] ++;
if(!sum)
{
dp[i] = 1;
if(siz[i] == 1) g[i] = 1;
else g[i] = qpow(siz[i],siz[i] - 2); // 和為 0 的連通塊（即只通過區間修（s_i += x && s_j -= x）就可以合法的集合），其合法的方案數為 $|S|^{|S| - 2}$
}
}
for(int i = 1;i < (1 << n);i ++) // S
{
if(!dp[i]) continue; // 考慮到和不為 0 的連通塊要特判。。。？
bool flag = 1;
for(int j = (i - 1) & i;j;j = (j - 1) & i) if(dp[j]){flag = 0;break;} // 枚舉子集
TAG[i] = flag; // 子集中不含有和為 0 的集合
}
for(int i = 1;i < (1 << n);i ++) // S
{
if(!dp[i]) continue; //
for(int j = i;j;j = (j - 1) & i) vis[j] = 0; // 容斥，保證處理的子集不會重
for(int j = (i - 1) & i;j;j = (j - 1) & i) //
{
if(TAG[j] && !vis[j]) // 如果其子集中不含有和為 0 的集合并且其沒有加過qwq
{
if(dp[j] + dp[i ^ j] > dp[i]) dp[i] = dp[j] + dp[i ^ j],g[i] = g[j] * g[i ^ j] % mod; // 枚舉子集然后直接統計
else if(dp[j] + dp[i ^ j] == dp[i]) g[i] = (g[i] + g[j] * g[i ^ j] % mod) % mod; // 如果有步驟相同的，計入方案數
for(int k = (i ^ j);k;k = (k - 1) & (i ^ j)) vis[k] = 1; // 標記好處理過的子集
}
}
}
for(int i = 0;i < (1 << n);i ++) ans1 = max(ans1,dp[i]); // 求最少行動數
ans1 = n - ans1;
if(ans1 == n) return cout << n << '\n' << 2 * qpow(n + 2,n - 1) * fac[ans1] % mod,0;
for(int i = 0;i < (1 << n);i ++)
{
if(dp[i] == n - ans1)
{
ans2 = (ans2 + g[i] * c[n - siz[i]] % mod) % mod;
}
}
ans2 = ans2 * fac[ans1] % mod;
cout << ans1 << '\n' << ans2 % mod;
return 0;
}
T4：王哥與數字（digit）
不會，咕咕。
與你的日常，便是奇跡
