Tag: 套路题

相关链接

题目传送门：https://community.topcoder.com/stat?c=problem_statement&pm=14573&rd=16882

题目大意

给定$n(n \le 10^9)$，问有多少组不同的$a^b=c^d$成立
要求$1 \le a,b,c,d \le n$

解题报告

假设$a^b=c^d$，我们在枚举到$gcd(a,c)$的时候计算
如果$gcd(a,c)=a=c$的话，贡献显然是$n$
所以我们枚举$gcd$只需要枚举到$\sqrt{n}$
又因为次数非常小，所以我们可以暴力算有多少种指数满足要求
于是总的复杂度大概是$\sqrt{n}$的

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int MOD = 1000000007;
const int N = 100000;

int gcd[100][100];
bool vis[N];

class PowerEquation {
    public:
    	int count(int n) {
    		memset(vis, 0, sizeof(vis));
    		for (int i=1;i<=50;i++) {
				for (int j=1;j<=50;j++) {
					gcd[i][j] = GCD(i, j);
				}
			}
			
			int ret = (LL)n * n % MOD, dec = 0;
    		for (int i=2;1;i++) {
				if (i * i > n) {
					ret = (ret + (n - i + 1ll - dec) * n) % MOD;
					break;	
				} else {
					if (vis[i]) continue;
					for (LL j=i*i;j<=n;j*=i) {
						if (j * j <= n) vis[j] = 1;
						else ++dec;
					}
					
					int mx = 1, tmp = 0; LL cur = i;
					while (cur * i <= n) cur *= i, ++mx;
					for (int a=1;a<=mx;a++) {
						for (int b=1;b<=mx;b++) {
							int c = max(b,a) / gcd[a][b];
							tmp = (tmp + n / c) % MOD;
						}
					} 
					ret = (ret + tmp) % MOD;
				}
			}
    	    return ret;
   		}
   	private:
   		int GCD(int a, int b) {
			return b? GCD(b, a%b): a;   
		}
};

相关链接

题目传送门：http://codeforces.com/contest/797/problem/D

解题报告

之前做过类似的题：http://oi.cyo.ng/?p=298
大概就是说，排序之后，每个点的左右子树切换至多发生一次
于是用基排来离散化的话，时间复杂度就是：$O(n)$的

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 200009;

int n,rt,is_rt[N],val[N],ch[N][2],TOT[N];
int tot,_hash[N],cnt[N],dep[N],vout;
set<pair<int,int> > id[N];

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

void dfs(int w, int f) {
	dep[w] = dep[f] + 1;
	if (ch[w][1]) dfs(ch[w][1], w);
	if (ch[w][0]) dfs(ch[w][0], w);
}

void add(int w, int sta) {
	if (w <= 0) return;
	id[val[w]].insert(make_pair(dep[w], w)); 
	cnt[val[w]]++;
	if (val[w] > sta) add(ch[w][0], sta);
	else add(ch[w][1], sta);
}

void del(int w, int sta) {
	if (w <= 0) return;
	id[val[w]].erase(make_pair(dep[w], w));
	cnt[val[w]]--;
	if (val[w] > sta) del(ch[w][0], sta);
	else del(ch[w][1], sta);
}

int main() {
	n = read();
	for (int i=1,l,r;i<=n;i++) {
		val[i] = read(); _hash[++tot] = val[i];
		if ((l = read()) != -1) ch[i][0] = l, is_rt[l] = 1;
		if ((r = read()) != -1) ch[i][1] = r, is_rt[r] = 1;
	}
	for (int i=1;i<=n;i++) if (!is_rt[i]) {rt = i; break;}
	dfs(rt, rt);
	sort(_hash+1, _hash+1+tot);
	tot = unique(_hash+1, _hash+1+tot) - _hash - 1;
	for (int i=1;i<=n;i++) val[i] = lower_bound(_hash+1, _hash+1+tot, val[i]) - _hash, TOT[val[i]]++;
	
	add(rt, 1);
	if (!cnt[1]) vout += TOT[1];
	for (int i=2,w;i<=tot;i++) {
		if (id[i].size() > 0) {
			auto tmp = id[i].begin();
			w = tmp->second;
			del(w, i-1);
			add(w, i);
		}
		if (cnt[i] == 0) vout += TOT[i];
	}	
	printf("%d\n",vout);
	return 0;
}

相关链接

题目传送门：https://www.codechef.com/problems/DINING
官方题解：https://discuss.codechef.com/questions/70332/dining-editorial

解题报告

这题套路啊，神™套路啊！

关键问题是它的概率是乘起来的，不是加起来
于是很多东西都不能用啊！
于是题解说我们可以取对数，因为$\log(a \cdot b) = \log (a) + \log (b)$
于是就变成了加法，于是就可以跑一个费用流了

把乘法换搞成加法，在模意义下还有一种做法，参见：
http://oi.cyo.ng/?p=2702

相关链接

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4810
神犇题解：http://blog.csdn.net/qzh_1430586275/article/details/69400458

解题报告

看一看似乎一脸懵逼啊
询问两数相加、相减为特殊值不是只能$FFT$吗？
你这™还带区间限制，那怎么做啊……

但仔细看看值域范围，发现这货只有$10^{10}$
配上$30s$的限制，刚好是$bitset$的数据范围啊！
于是仔细想一想，加法可以直接减法可以直接左移然后$and$起来
至于减法，我们可以记一下负数就可以转化为减法了
至于相乘嘛，我们可以暴力枚举因数！
于是再配上区间的莫队，时间复杂度：$O(n \sqrt{n} + \frac{mc}{64})$

相关链接

题目传送门：http://codeforces.com/problemset/problem/167/E
神犇题解：http://blog.csdn.net/popoqqq/article/details/45046545

吐槽

神™套路题，考试考这个也是简直了
出题人你能不能良心一点 (╯‵□′)╯︵┻━┻

还有一个高一神犇各种瞎搞给做出来了……
牛逼！我就服你！

解题报告

我们可以把给的出发点到目标点配对之后重新标号
于是我们可以看成是一个置换
然后我们考虑在每一个交叉的位置交换那两条路径的目标点
于是这个方案的置换奇偶性一定改变

然后我们考虑如果一套路径方案交叉了奇数次，那么这是一个奇置换，算行列式时系数为$-1$
如果一套路径的方案交叉了偶数次，那么这是一个偶置换，算行列式的时候系数为$1$
这刚好和容斥的系数对上！于是我们算出行列式就相当于用容斥算出了答案

现在回到行列式的定义：$|A|= \sum\limits_{\sigma\in Sn}{{\mathop{\rm sgn}}(\sigma)\prod\limits_{i= 1}^n{{a_{i,\sigma(i)}}}}$
系数已经没有问题了，那么看方案数的统计，我们发现设$f_{i,j}$为$i \to j$的方案数
放到矩阵的对应位置上，刚好又能对上方案数，于是什么都对上了，这题算个行列式就完了

相关链接

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3028
神犇题解：http://blog.csdn.net/regina8023/article/details/44995939

解题报告

这题看上去一眼不可做啊！第一反应：还要写高精？
但想一想似乎物品非常妙妙：

我们强行将其分为四组：{汉堡，可乐} {蜜桃多，土豆片炒肉} {包子，鸡块} {鸡腿，面包}
我们发现每一组都能凑出每一个自然数，且方案唯一
于是问题变为将$n$个球分为$4$组，每组可以为空的方案数

这是插板法的经典问题，于是搞一个组合数就可以了
什么组合数太大？
我们注意到答案实际是$\frac{n^{\bar 3}}{6}$，所以我们取个模就可以了

当然你也可以强行搞生成函数然后泰勒展开得到一样的结论
但我不会泰勒展开 QwQ

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int MOD = 10007;
const int REV = 1668;

int main() {
	int n=0; char pat[600]; cin>>pat+1;
	for (int i=1;i<=strlen(pat+1);i++)
		n = (n * 10 + pat[i] - '0') % MOD;
	cout<<n*(n+1ll)*(n+2)*REV%MOD;
	return 0;
}

题目大意

给定一个$n(n \le 100)$个点的连通图
不同顶点之间有$n^2$个最小割
现在给定这$n^2$个最小割，让你构造一个图使其满足条件

解题报告

据说这是论文题？

因为任意两点间的最小割可以用最小割树来表示
所以我们考虑构造一个树形结构

因为一条路径上的最小割相当于取$min$，所以流量大的不会影响流量小的
所以我们先按边权从大到小排序
如果当前这条边的两个端点已经在一个连通块内，那么暴力判断是否符合要求
如果不在一个块内，那么连一条边

至于为什么这样是对的，因为已经按权值排序了
如果不在一个连通块内，还不连边，那么最终连通这两块的权值一定大于要求的最小割，所以必须立刻连边
至于已经连边了还冲突的话，因为之前的边都是必要的，所以也没有调整的需要，一定是无解的

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
const int N = 109;
const int M = N * N << 1;
const int INF = 1e9;
 
int n,tot,head[N],nxt[M],to[M],cost[M],fa[N];
struct Data{
    int u,v,val;
    inline Data() {}
    inline Data(int a, int b, int c):u(a),v(b),val(c) {}
    inline bool operator < (const Data &B) const {
        return val > B.val;
    }
}p[N*N*N];
 
inline int read() {
    char c=getchar(); int ret=0,f=1;
    while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
    while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
    return ret * f;
}
 
inline void AddEdge(int u, int v, int c) {
    static int E = 1; cost[E+1] = cost[E+2] = c; 
    to[++E] = v; nxt[E] = head[u]; head[u] = E;
    to[++E] = u; nxt[E] = head[v]; head[v] = E;
}
 
int cal(int w, int f, int pur, int mn) {
    if (w == pur) return mn;
    for (int i=head[w],tmp;i;i=nxt[i]) {
        if (to[i] != f) {
            tmp = cal(to[i], w, pur, min(mn, cost[i]));
            if (~tmp) return tmp;
        }
    } return -1;
}
 
int find(int x) {return x==fa[x]? x: fa[x]=find(fa[x]);}
 
int main() {
    n = read();
    for (int i=1,v;i<=n;i++) {
        fa[i] = i;
        for (int j=1;j<=n;j++) {
            if (v=read(), i==j) continue;
            p[++tot] = Data(i, j, v);   
        }
    }
    sort(p+1, p+1+tot);
    for (int i=1;i<=tot;i++) {
        int u=p[i].u, v=p[i].v, val=p[i].val;
        if (find(u) == find(v)) {if(cal(u,u,v,INF)!=val)cout<<-1,exit(0);}
        else fa[find(u)] = fa[v], AddEdge(u, v, val);
    }
    cout<<n-1<<endl;
    for (int i=2;to[i];i+=2) printf("%d %d %d\n",to[i],to[i+1],cost[i]);
    return 0;
}

相关链接

题目传送门：http://oi.cyo.ng/wp-content/uploads/2017/03/20170301145817_34363.png
官方题解：http://oi.cyo.ng/wp-content/uploads/2017/03/20170301150237_94661.png

一句话题意

给$n_1$个$A$，$n_2$个$B$，$n_3$个$C$，$n_4$个$D$
问有多少种排列方式，使得相邻两项全部不同
$n_1,n_2,n_3,n_4 \le 10^3$

吐槽

因为做过魔法的碰撞
所以这题卡在$O(n^3)$的复杂度上卡了三个半小时 QwQ
最后暴力还$MLE$了 QwQ

解题报告

假设我们知道了将$A,B$分成$i$段、每一段中相邻两项不同的方案数为$f_i$
知道了将$C,D$分成$i$段、每一段中相邻两项不同的方案数为$g_i$
那么答案显然为$\sum\limits_{i=1}^{n_1+n_2}{f_i \cdot (g_{i-1}+2g_i+g_{i+1})}$
至于中间那一项为什么要乘以2？ 因为多出来那一段我们既可以放段首，也可以放段尾

现在唯一的问题就是如何求出$f_i,g_i$了
考虑仅由$A,B$组成的字符串，一定为以下四种情况之一

[1]ABAB…A
[2]BABA…B
[3]ABAB…B
[4]BABA…A

假如我们枚举第一种情况出现了$i$次
那么第二种情况的出现次数$j=i-(a-b)$
那剩下的$k$次，就是第三种和第四种了，不难发现我们乘上$2^k$之后他们就可以视为等价
于是我们先在第一种情况的位置上插入$A$,第二种情况插入$B$，第三、四种情况插入$AB(BA)$
之后我们相当于把剩下的$A,B$两两配对，然后分成$x$组，允许空集
那么这就是插板法的板题了

于是我们就用上述算法处理出$f_i,g_i$即可
时间复杂度：$O(n^2)$

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int MOD = 1000000007;
const int N = 2009;

int vout,f[N],g[N],C[N][N],PW2[N];

inline int read() {
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

inline int solve(int a, int b, int c) {
	if (a < b) swap(a, b);
	if (!a && b) return b == c;
	int ret = 0;
	for (int i=a-b,j,k;i<=c;++i) {
		j = i - a + b; k = c - i - j;
		if (j >= 0 && k >= 0 && a >= i + k ) {
			(ret += (((LL)C[i] * C[j][c-i] % MOD) * PW2[k] % MOD) * C[c-1][a-i-k+c-1] % MOD) %= MOD;
		}
	}
	return ret;
}

int main() {
	PW2[0] = 1; for (int i=1;i<N;i++) PW2[i] = (PW2[i-1] << 1) % MOD;
	C[0][0] = 1; for (int i=1;i<N;i++) {
		C[0][i] = 1; for (int j=1;j<=i;j++) {
			C[j][i] = (C[j-1][i-1] + C[j][i-1]) % MOD;
		}
	} 
	int a=read(),b=read(),c=read(),d=read();
	if (a + b == 0) f[1] = 1;
	else for (int i=1;i<=a+b;i++) f[i] = solve(a, b, i);
	if (c + d == 0) g[1] = 1;
	else for (int i=1;i<=c+d;i++) g[i] = solve(c, d, i);
	for (int i=1;i<=a+b;i++) (vout += f[i] * (g[i-1] + 2ll * g[i] + g[i+1]) % MOD) %= MOD;
	printf("%d\n",vout);
	return 0;
}