Tag: 好题

相关链接

题目传送门：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=2118
神犇题解：https://blog.sengxian.com/solutions/bzoj-2118

解题报告

先来看一道简单的题目：

给定$a,b,c(a,b,c \le 10^5)$，规定$x,y,z \in \mathbb{N}$
问$ax+by+cz$不能表示出的正整数中，最大的那一个是多少

我们不妨在$\bmod c$的意义下做，这样就可以只考虑$0 \sim c-1$
于是暴力用$a,b$连边，跑一边最短路
这样就可以求出在$\bmod c$的剩余系中，每一个等价类最早出现的位置
于是扫一遍，取一个$\max$就可以了

然后再看看这个题，也就是多连几条边的事吧？

Code

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

const int N = 500009;
const int M = N * 12;
const LL INF = 1e17;

int n,a[N],done[N];
int nxt[M],to[M],cost[M],head[N];
LL dis[N],bmn,bmx,mn=INF;
priority_queue<pair<LL,int> > que;

inline void AddEdge(int u, int v, int c) {
	static int E = 1; cost[++E] = c;
	to[E] = v; nxt[E] = head[u]; head[u] = E;
}

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;
}

inline void Dijkstra() {
	for (int i=0;i<mn;i++) dis[i] = INF;
	dis[0] = 0; que.push(make_pair(0, 0));
	while (!que.empty()) {
		int w = que.top().second; que.pop();
		if (done[w]) continue; else done[w] = 1;
		for (int i=head[w];i;i=nxt[i]) {
			if (dis[to[i]] > dis[w] + cost[i]) {
				dis[to[i]] = dis[w] + cost[i];
				que.push(make_pair(-dis[to[i]], to[i]));
			}
		}
	}
}

inline LL cal(LL lim) {
	LL ret = 0, tmp;
	for (int i=0;i<mn;i++) {
		if (lim < dis[i]) continue;
		ret += (lim - dis[i]) / mn + 1;
	}
	return ret;
}

int main() {
	n = read(); cin>>bmn>>bmx;
	for (int i=1;i<=n;i++) {
		a[i] = read();
		if (a[i]) mn = min(mn, (LL)a[i]);
	}
	for (int i=1;i<=n;i++) {
		if (a[i] == mn) continue;
		for (int j=0;j<mn;j++) {
			AddEdge(j, (j+a[i])%mn, a[i]);
		}
	}
	Dijkstra();
	printf("%lld\n",cal(bmx)-cal(bmn-1));
	return 0;
}

相关链接

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

解题报告

这个东西，看一看样例，感觉答案是$2^k$，然后写一发无脑贪心就过了

不过这题的证明非常妙妙啊：

考虑将每一个$0 \sim 2^{k+1}-1$的数看成一个点，标号为这个数
把在这个数末尾或者开头加$0/1$看作边
那么每个点度数恰好为$4$，并且整个图显然连通
那么这图显然存在欧拉回路，那么就能够一笔画

于是在这个图上贪心走就可以了

Code

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

const int N = 3000;

int n,k,arr[N];
set<int> S;

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;
}

inline int get(int p) {
	int ret = 0;
	for (int i=0;i<k;i++) ret += (1 << i) * arr[p + i];
	return ret; 
}

int main() {
	k = read(); n = 1 << k;
	for (int i=1;i<=k;i++) arr[i] = 0; S.insert(0);
	for (int i=n;i>n-k;i--) arr[i] = 1, S.insert(get(i));
	for (int i=2;i<=n-k;i++) {
		if (S.count(get(i))) arr[i+k-1] = 1;
		S.insert(get(i));
	}
	printf("%d ",n);
	for (int i=1;i<=n;i++) printf("%d",arr[i]);
	return 0;
}

相关链接

题目传送门：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://acm.hdu.edu.cn/showproblem.php?pid=5772
神犇题解：http://www.cnblogs.com/qscqesze/p/5715939.html

解题报告

日常看错题系列：

1. 子序列看成子串
2. 值域范围$0 \sim 9$看漏

于是只会跑$n$遍网络流的算法了 QwQ
大概就是枚举左端点，然后暴力跑

考虑原题的话，唯一的Trick就是如何处理一个数第一次选的代价不同
我们可以使用最大权闭合子图来解决这个问题：

每一类数字新建一个结点，权值为$b_i – a_i$
值为该数字的所有序列上的点向这个新建的点连一条有向边

至于本题的其他部分就没什么好玩的了

相关链接

题目传送门：https://www.codechef.com/problems/PARADE
神犇题解：http://blog.csdn.net/jasonvictoryan/article/details/53395098

解题报告

这题先只考虑一个询问的情况

这显然可以使用拆点+二分图最大权匹配去做
具体来说：每个点拆成出度和入度两个点，然后出度放左边，入度放右边
考虑每找到一条增广路，就是在原图中走了一条边
那么不管是连接了两条路径，或是新走到一个点，都会使总费用减少一个$C$
但每走一次增广路，都会花费一些费用$v$
显然我们应该在$v > C$的时候停止增广

现在考虑多个询问
因为是费用流算法，所以单次增广的费用$v_i$是单调不减的
于是我们可以记录每一次增广的$v_i$。对于询问就二分，然后求前缀和就好
当然不想二分，也可以先排个序然后扫一遍，反正总的时间复杂度主要还是卡在费用流那里

相关链接

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

解题报告

最开始一眼看成神题，还在想$SDOI$这是要赶超$ZJOI$的节奏啊
然后就发现看漏条件了 _(:з」∠)_

因为每一次只能交换一个$2^k$的块，并且$2$的不同次幂之间不会相互影响
话一句话来说，考虑交换长度为$2^k$的块时，所有长度为$2^{k-1}$的块的顺序必须已经排好
且长度为$2^k$的块，只能有至多两块位置不对
于是我们搞一发$DFS$就好了，时间复杂度：$O(n \log n)$