NOI 2016 Day1 题解
2024-09-07 23:40:40
今天写了NOI2016Day1的题，来写一发题解。
T2 网格
Description
\(T\) 次询问，每次给出一个 \(n\times m\) 的传送门，上面有 \(c\) 个位置是蛐蛐，其余位置都是跳蚤，问至少要把多少个跳蚤换成蛐蛐才能使存在两只跳蚤不连通。
\(n,m\le 10^9,\sum c\le 10^5\)
Solution
可以想到的是答案一定是 \(-1,0,1,2\) 中的一个。
考虑如何判断。\(0\) 的话一定是存在两个及以上的跳蚤连通块，\(1\) 的话是只存在一个跳蚤连通块且存在一个割点，\(-1\) 就不用说了。\(2\) 就是除了这些情况的其他情况。
考虑如何快速判断。首先我们可以发现有用的其实只有在蛐蛐周围 \(5\times 5\) 的这些格子。
然后我们可以发现如果存在两个及以上的连通块，那么一定存在一个蛐蛐连通块使得周围有属于不同的跳蚤联通块的跳蚤。
于是我们就可以做到 \(\Theta(\sum c)\) 了。注意因为常数较大所以需要使用 \(\text{hash}\) 表。
Code
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define Int register int
#define mp make_pair
#define MAXN 2500005
template <typename T> inline void read (T &t){t = 0;char c = getchar();int f = 1;while (c < '0' || c > '9'){if (c == '-') f = -f;c = getchar();}while (c >= '0' && c <= '9'){t = (t << 3) + (t << 1) + c - '0';c = getchar();} t *= f;}
template <typename T,typename ... Args> inline void read (T &t,Args&... args){read (t);read (args...);}
template <typename T> inline void write (T x){if (x < 0){x = -x;putchar ('-');}if (x > 9) write (x / 10);putchar (x % 10 + '0');}
int kase,n,m,c;
struct Hash{//实现hash表
private:
#define mod 1000007
#define int long long
int siz,sx[MAXN],sy[MAXN],nxt[MAXN],ind[MAXN],head[mod + 5];
public:
void clear(){siz = 0,memset (head,0,sizeof (head));}
void ins (int x,int y,int id){
int pos = (1ll * (x - 1) * m + y) % mod;
sx[++ siz] = x,sy[siz] = y,ind[siz] = id,nxt[siz] = head[pos],head[pos] = siz;
}
int query (int x,int y){
int pos = (1ll * (x - 1) * m + y) % mod;
for (Int i = head[pos];i;i = nxt[i]) if (sx[i] == x && sy[i] == y) return ind[i];
return 0;
}
#undef int
}h,bel,vis;
struct edge{
int v,nxt;
}e[MAXN * 4];
int toop = 1,head[MAXN];
void link (int u,int v){
e[++ toop] = edge {v,head[u]},head[u] = toop;
e[++ toop] = edge {u,head[v]},head[v] = toop;
}
bool cut[MAXN];
int ind,dfn[MAXN],low[MAXN];
void Tarjan (int u,int fa){
dfn[u] = low[u] = ++ ind;int son = 0;
for (Int i = head[u];i;i = e[i].nxt){
int v = e[i].v;
if (!dfn[v]) son ++,Tarjan (v,u),low[u] = min (low[u],low[v]),cut[u] |= (low[v] >= dfn[u]);
else low[u] = min (low[u],dfn[v]);
}
if (!fa && son == 1) cut[u] = 0;
}
pii t[MAXN];
int dx[8] = {1,-1,0,0,1,1,-1,-1},dy[8] = {0,0,1,-1,1,-1,1,-1};
bool inside (int x,int y){return x >= 1 && x <= n && y >= 1 && y <= m;}
bool checkit (){//判断唯二的两个点是否联通
for (Int x = 1;x <= n;++ x)
for (Int y = 1;y <= m;++ y) if (!h.query (x,y)){
for (Int i = 0;i < 4;++ i){
int tx = x + dx[i],ty = y + dy[i];
if (inside (tx,ty) && !h.query (tx,ty)) return 0;
}
}
return 1;
}
bool ner[MAXN];
int Abs (int x){return x < 0 ? -x : x;}
queue <pii> Q,q;
void BFS (int sx,int sy,int col){
Q.push (mp (sx,sy)),bel.ins (sx,sy,col);
while (!Q.empty()){
int x = Q.front().first,y = Q.front().second;Q.pop ();
for (Int i = 0;i < 4;++ i){
int tx = x + dx[i],ty = y + dy[i];
if (inside (tx,ty) && h.query (tx,ty) > 0 && !bel.query (tx,ty))
bel.ins (tx,ty,col),Q.push (mp (tx,ty));
}
}
}
int tot;
pii pnt[MAXN];
bool BFS1 (int sx,int sy){
tot = 0;Q.push (mp (sx,sy)),vis.ins (sx,sy,-1);
while (!Q.empty()){
int x = Q.front().first,y = Q.front().second;Q.pop ();
for (Int i = 0;i < 8;++ i){
int tx = x + dx[i],ty = y + dy[i];
if (inside (tx,ty) && h.query (tx,ty) == -1 && !vis.query (tx,ty))
vis.ins (tx,ty,-1),Q.push (mp (tx,ty));
else if (inside (tx,ty) && h.query (tx,ty) > 0 && !vis.query (tx,ty)) pnt[++ tot] = mp (tx,ty);
}
}
if (!tot) return 0;
for (Int i = 2,tmp = bel.query (pnt[1].first,pnt[1].second);i <= tot;++ i)
if (bel.query (pnt[i].first,pnt[i].second) != tmp) return 1;
return 0;
}
bool fuckit(){
int fuc = 0;bel.clear ();
while (!q.empty()){
int x = q.front().first,y = q.front().second;q.pop ();
if (bel.query (x,y)) continue;
BFS (x,y,++ fuc);
}
vis.clear ();
for (Int i = 1;i <= c;++ i)
if (!vis.query (t[i].first,t[i].second))
if (BFS1 (t[i].first,t[i].second)) return 1;
return 0;
}
signed main(){
read (kase);
while (kase --> 0){
while (!q.empty()) q.pop();
read (n,m,c);int cnt = 0;h.clear ();
for (Int i = 1;i <= c;++ i) read (t[i].first,t[i].second),h.ins (t[i].first,t[i].second,-1);
if (c >= 1ll * n * m - 1){puts ("-1");continue;}
else if (c == 1ll * n * m - 2){puts (checkit () ? "0" : "-1");continue;}
toop = 1,memset (head,0,sizeof (head));
for (Int z = 1;z <= c;++ z){
int x = t[z].first,y = t[z].second;
for (Int tx = max (1,x - 2);tx <= min (n,x + 2);++ tx)
for (Int ty = max (1,y - 2);ty <= min (m,y + 2);++ ty){
if (!h.query (tx,ty)){
h.ins (tx,ty,++ cnt),ner[cnt] = max (Abs (tx - x),Abs (ty - y)) <= 1,q.push (mp (tx,ty));
for (Int i = 0;i < 4;++ i){
int x1 = tx + dx[i],y1 = ty + dy[i];
if (inside (x1,y1) && h.query (x1,y1) > 0) link (cnt,h.query (x1,y1));
}
}
else if (h.query (tx,ty) > 0 && max (Abs (tx - x),Abs (ty - y)) <= 1) ner[h.query (tx,ty)] = 1;
}
}
if (fuckit ()){puts ("0");continue;}
if (n == 1 || m == 1){puts ("1");continue;}
ind = 0;for (Int i = 1;i <= cnt;++ i) cut[i] = dfn[i] = 0;
for (Int i = 1;i <= cnt;++ i) if (!dfn[i]) Tarjan (i,0);
for (Int i = 1;i <= cnt;++ i) if (cut[i] && ner[i]){puts ("1");goto there;}
puts ("2");
there:;
}
return 0;
}
T3 循环之美
Description
给出 \(n,m,k\)，求出 \(a,b\) 满足 \(1\le a\le n,1\le b\le m\) 且 \(a/b\) 在 \(k\) 进制下小数部分纯循环的本质不同个数。
\(n,m\le 10^9,k\le 2000\)
Solution
首先可以观察到的是，当 \(\gcd(a,b)=1\) 且 \(\gcd(b,k)=1\)的时候会产生贡献。
然后就是莫反推式子了：
\[\sum_{a=1}^{n}\sum_{b=1}^{m}[\gcd(a,b)=1][\gcd(b,k)=1]
\]
\]
\[=\sum_{b=1}^{m} [\gcd(b,k)=1]\sum_{d|b} \mu(d)\times \lfloor\frac{n}{d}\rfloor
\]
\]
\[=\sum_{d=1}^{\min(n,m)} \mu(d)\times \lfloor\frac{n}{d}\rfloor\sum_{b=1}^{\lfloor\frac{m}{d}\rfloor} [\gcd(k,db)=1]
\]
\]
\[=\sum_{d=1}^{n} \mu(d)\times \lfloor\frac{n}{d}\rfloor\times [\gcd(d,k)=1] \sum_{b=1}^{\lfloor\frac{m}{d}\rfloor} [\gcd(b,k)=1]
\]
\]
然后你发现后面那一坨可以直接 \(\Theta(k\log k)\) 预处理，然后考虑前面怎么弄。
设 \(g(N,K)=\sum_{d=1}^{N} \mu(d)[\gcd(d,K)=1]\)
那么可以得到 \(g(N,K)=\sum_{d=1}^{N} \mu(d)\sum_{h|d\wedge h|k} \mu(h)\)
\[=\sum_{h|k} \mu^2(h)\sum_{d=1}^{\lfloor\frac{N}{h}\rfloor} \mu(d)[\gcd(d,h)=1]
\]
\]
\[=\sum_{h|k} \mu^2(h)g(\lfloor\frac{N}{h}\rfloor,h)
\]
\]
边界条件就是 \(g(N,0)=0,g(N,1)=\sum_{i=1}^{N} \mu(i)\)，这个可以直接杜教筛。
总的复杂度我不是很会算，据说是 \(\Theta(k\log k+n^{2/3}+d(k)\times \sqrt n)\) 的，其中 \(d(k)\) 表示 \(k\) 的质因子个数。
Code
#include <unordered_map>
#include <bits/stdc++.h>
using namespace std;
#define Int register int
#define int long long
#define MAXN 1000005
template <typename T> inline void read (T &t){t = 0;char c = getchar();int f = 1;while (c < '0' || c > '9'){if (c == '-') f = -f;c = getchar();}while (c >= '0' && c <= '9'){t = (t << 3) + (t << 1) + c - '0';c = getchar();} t *= f;}
template <typename T,typename ... Args> inline void read (T &t,Args&... args){read (t);read (args...);}
template <typename T> inline void write (T x){if (x < 0){x = -x;putchar ('-');}if (x > 9) write (x / 10);putchar (x % 10 + '0');}
int n,m,k;
int gcd (int a,int b){return !b ? a : gcd (b,a % b);}
bool vis[MAXN];
int tot,mu[MAXN],pre[MAXN],prime[MAXN];
void Euler (int up){
mu[1] = pre[1] = 1;
for (Int i = 2;i <= up;++ i){
if (!vis[i]) prime[++ tot] = i,mu[i] = -1;
for (Int j = 1;j <= tot && i * prime[j] <= up;++ j){
vis[i * prime[j]] = 1;
if (i % prime[j] == 0) break;
else mu[i * prime[j]] = -mu[i];
}
pre[i] = pre[i - 1] + mu[i];
}
}
unordered_map <int,int> mp;
int Getmu (int N){
if (N <= 1e6) return pre[N];
if (mp.find(N) != mp.end()) return mp[N];
int res = N >= 1;
for (Int l = 2,r;l <= N;l = r + 1)
r = N / (N / l),res -= (r - l + 1) * Getmu (N / l);
return mp[N] = res;
}
#define MAXM 2005
vector <int> vic[MAXM];
unordered_map <int,int> g[MAXM];
int getit (int N,int K){
if (K == 0 || N <= 0) return 0;
if (g[K].find (N) != g[K].end()) return g[K][N];
if (K == 1) return g[K][N] = Getmu (N);
int res = 0;
for (Int h : vic[K]) res += mu[h] * mu[h] * getit (N / h,h);
return g[K][N] = res;
}
int f[MAXM];
int getf (int N){
return (N / k) * f[k] + f[N % k];
}
signed main(){
read (n,m,k),Euler (1e6);
for (Int d = 1;d <= k;++ d) f[d] = f[d - 1] + (gcd (d,k) == 1);
for (Int d = 1;d <= k;++ d) if (mu[d]) for (Int K = d;K <= k;K += d) vic[K].push_back (d);
int tot = 0;
for (Int l = 1,r,las = 0,tmp;l <= min (n,m);l = r + 1)
r = min (n / (n / l),m / (m / l)),tmp = getit (r,k),
tot += (tmp - las) * getf (m / l) * (n / l),las = tmp;
write (tot),putchar ('\n');
return 0;
}
最新文章
- 悟透JavaScript（理解JS面向对象的好文章）
- 嵌入式Linux应用程序开发详解------（创建守护进程）
- Oracle存储过程中传入参数，传出字符串
- （3）初次接触off
- Canvas入门（1）：绘制矩形、圆、直线、曲线等基本图形
- 飘逸的python - 一个最简单的服务器
- reinterpret_cast应用
- HDU - 2802 F(N) （周期）
- alert 执行顺序问题
- AtCoder Regular Contest 077
- iOS 8 中如何集成 Touch ID 功能
- mssql sqlserver updatetext关键字应用简介说明
- Java WebService接口生成和调用 图文详解>【转】【待调整】
- echart的x换行
- [04-01]css组合选择器
- .bat文件调用java类的main方法
- struts框架之总结OGNL表达式的特殊的符号
- centos6下时间同步（ntp）操作
- Javascript计算星座
- 题解【bzoj2440 [中山市选2011]完全平方数】