test20190905

发表于

闲扯

今天的题真是毒瘤啊。

$@ChiTongZ$ 出来挨打！！

题面

题面

$T1$

Solution

对于每次查询，我们相当于是知道了两个区间的关系。（即区间 $1\sim r$ 和区间 $1\sim l+1$ 的奇偶关系）

而对于两组关系，如果他们有相同的断点，是可以传递的。

例如我们知道了 $x,y$ 的关系，同时还知道了 $x,z$ 的关系，那么我们是可以推出 $y,z$ 的关系的。（为了方便，这里的 $x$ 表示区间 $1\sim x$ ）

而我们最终要求的是每一组 $i$ 和 $i+1$ 的关系。

对于这种关系可以传递的东西，可以使用并查集维护。

这样问题就变成了用最小的代价，使得所有的点都存在于同一个集合里。

看着是不是很眼熟？没错，就是求一个最小生成树

Code

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
64
65
#include<bits/stdc++.h>
#define del(a,i) memset(a,i,sizeof(a))
#define ll long long
#define inl inline
#define il inl void
#define it inl int
#define ill inl ll
#define re register
#define ri re int
#define rl re ll
#define mid ((l+r)>>1)
#define lowbit(x) (x&(-x))
#define INF 0x3f3f3f3f
using namespace std;
template<class T>il read(T &x){
	int f=1;char k=getchar();x=0;
	for(;k>'9'||k<'0';k=getchar()) if(k=='-') f=-1;
	for(;k>='0'&&k<='9';k=getchar()) x=(x<<3)+(x<<1)+k-'0';
	x*=f;
}
template<class T>il print(T x){
	if(x/10) print(x/10);
	putchar(x%10+'0');
}
ll mul(ll a,ll b,ll mod){long double c=1.;return (a*b-(ll)(c*a*b/mod)*mod)%mod;}
it qpow(int x,int m,int mod){
	int res=1,bas=x%mod;
	while(m){
		if(m&1) res=(1ll*res*bas)%mod;
		bas=(1ll*bas*bas)%mod,m>>=1;
	}
	return res%mod;
}
const int MAXN = 3e3+5;
int n,cnt,num,fa[MAXN];
ll ans;
struct Node{
	int val,l,r;
	bool operator <(const Node &t) const{
		return val<t.val;
	}
}node[MAXN/2*MAXN];
it find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
il merge(int x,int y){if(find(x)!=find(y)) fa[find(x)]=find(y);}
int main(){
	freopen("game.in","r",stdin);
	freopen("game.out","w",stdout);
	read(n);
	for(ri i=1;i<=n+1;++i) fa[i]=i;
	for(ri i=1;i<=n;++i)
		for(ri j=i;j<=n;++j){
			read(node[++cnt].val);
			node[cnt].l=i,node[cnt].r=j+1;
		}
	sort(node+1,node+1+cnt);
	for(ri i=1;i<=cnt;++i){
		ri x=node[i].l,y=node[i].r;
		if(find(x)==find(y)) continue;
		merge(x,y),cnt++;
		ans+=node[i].val;
		if(cnt==n) break;
	}
	print(ans);
	return 0;
}

$T2$

Solution

考虑搜索，但是时间复杂度太高，所以模拟退火优化，卡一卡。

每次找两个格子，交换位置，答案更优就保留，否则按照某个随着随机次数增多而减小的概率保留答案。

Code

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include <cstdio>
#include <limits.h>
#include <time.h>
#include <algorithm>
#include <cstring>
#include <math.h>
#include <iostream>

using namespace std;

inline int ABS (int u) { return u >= 0 ? u : -u; }
inline void swap (int&a, int&b) {
	int c = a;
	a = b,
	b = c;
}

const int N = 25;
const double delta = 0.99999;
int mp[N][N], n, m, c, p[N], ans = INT_MAX, tmp[N][N];

inline void init () {
	ans = INT_MAX;
}

inline void MAKE () {
	static int tp[N];
	for (int i = 1; i <= c; ++i) tp[i] = p[i];
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			mp[i][j] = rand () % c + 1;
			while (!tp[mp[i][j]]) mp[i][j] = rand () % c + 1;
			tp[mp[i][j]]--;
		}
	}
}

inline int CONTRIBUTE (int x, int y, int k) {
	if (k == 1) {
		int res = 0;
		if (x != 1 && mp[x][y] != mp[x - 1][y]) res += mp[x][y] * mp[x][y];
		if (x != n && mp[x][y] != mp[x + 1][y]) res += mp[x][y] * mp[x][y];
		if (y != 1 && mp[x][y] != mp[x][y - 1]) res += mp[x][y] * mp[x][y];
		if (y != m && mp[x][y] != mp[x][y + 1]) res += mp[x][y] * mp[x][y];
		return res;
	}
	int res = 0;
	if (x != 1 && mp[x][y] != mp[x - 1][y]) res += mp[x][y] * mp[x][y] + mp[x - 1][y] * mp[x - 1][y];
	if (x != n && mp[x][y] != mp[x + 1][y]) res += mp[x][y] * mp[x][y] + mp[x + 1][y] * mp[x + 1][y];
	if (y != 1 && mp[x][y] != mp[x][y - 1]) res += mp[x][y] * mp[x][y] + mp[x][y - 1] * mp[x][y - 1];
	if (y != m && mp[x][y] != mp[x][y + 1]) res += mp[x][y] * mp[x][y] + mp[x][y + 1] * mp[x][y + 1];
	return res;
}

inline int RAND (int l, int r) {
	return rand () % (r - l + 1) + l;
}

inline void SA () {
	MAKE ();
	int tmpans = 0;
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j)
			tmpans += CONTRIBUTE (i, j, 1);
	if (tmpans < ans) {
		ans = tmpans;
		for (int i = 1; i <= n; ++i) {
			for (int j = 1; j <= m; ++j) {
				tmp[i][j] = mp[i][j];
			}
		}
	}
	double t = 1000000.00;
	while (t > 1e-15) {
		int ox = RAND (1, n), oy = RAND (1, m), nx = RAND (1, n), ny = RAND (1, m);
		int newans = tmpans;
		newans -= CONTRIBUTE (ox, oy, 2), newans -= CONTRIBUTE (nx, ny, 2);
		swap (mp[ox][oy], mp[nx][ny]);
		newans += CONTRIBUTE (ox, oy, 2), newans += CONTRIBUTE (nx, ny, 2);
		if (newans < tmpans) {
			tmpans = newans;
		}
		else {
			int gap = newans - tmpans;
			if (exp (-t/((double)gap)) * RAND_MAX <= rand ()) {
				tmpans = newans;
			}
			else {
				swap (mp[ox][oy], mp[nx][ny]);
			}
		}
		if (tmpans < ans) {
			ans = tmpans;
			for (int i = 1; i <= n; ++i) {
				for (int j = 1; j <= m; ++j) {
					tmp[i][j] = mp[i][j];
				}
			}
		}
		t *= delta;
	}
	if (tmpans < ans) {
		ans = tmpans;
		for (int i = 1; i <= n; ++i) {
			for (int j = 1; j <= m; ++j) {
				tmp[i][j] = mp[i][j];
			}
		}
	}
}

int main () {
	freopen ("matrix.in", "r", stdin);
	freopen ("matrix.out", "w", stdout);
	ans = INT_MAX;
	srand (2345678);
	scanf ("%d%d%d", &n, &m, &c);
	for (int i = 1; i <= c; ++i) scanf ("%d", &p[i]);
	for (int i = 1; i <= 2; ++i) SA ();
	printf ("%d\n", ans);
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			printf ("%d ", tmp[i][j]);
		}
		puts ("");
	}
	fclose (stdin); fclose (stdout);
	return 0;
}

$T3$

Solution

对于 $90\%$ 的数据，我们可以用 $DP$ 解决。

设 $dp_{i,j}$ 表示第 $i$ 个节点，乘积为 $j$ 的方案数。

那么由子树向上维护时，得到转移方程 $dp_{u,k}=\sum_{ij=k}dp_{u,i}dp_{v,j}$ 。

由于运算过程中会出现覆盖，影响之后的计算，所以我们另外开一个数组来储存。

至于满分做法，使用 $NTT$ 来快速求解。

所以还是咕咕咕了吧

Code

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
64
65
66
67
68
#include<bits/stdc++.h>
#define del(a,i) memset(a,i,sizeof(a))
#define ll long long
#define inl inline
#define il inl void
#define it inl int
#define ill inl ll
#define re register
#define ri re int
#define rl re ll
#define mid ((l+r)>>1)
#define lowbit(x) (x&(-x))
#define INF 0x3f3f3f3f
using namespace std;
template<class T>il read(T &x){
	int f=1;char k=getchar();x=0;
	for(;k>'9'||k<'0';k=getchar()) if(k=='-') f=-1;
	for(;k>='0'&&k<='9';k=getchar()) x=(x<<3)+(x<<1)+k-'0';
	x*=f;
}
template<class T>il print(T x){
	if(x/10) print(x/10);
	putchar(x%10+'0');
}
ll mul(ll a,ll b,ll mod){long double c=1.;return (a*b-(ll)(c*a*b/mod)*mod)%mod;}
it qpow(int x,int m,int mod){
	int res=1,bas=x%mod;
	while(m){
		if(m&1) res=(1ll*res*bas)%mod;
		bas=(1ll*bas*bas)%mod,m>>=1;
	}
	return res%mod;
}
const int MAXN = 3e5+5,mod = 998244353;
int n,p,u,v,b[MAXN],c[MAXN],head[MAXN],num_edge,dp[MAXN][105],tmp[105];
it add(int x,int y){return ((x+y)%mod+mod)%mod;}
struct Edge{
	int next,to;
	Edge(){}
	Edge(int next,int to):next(next),to(to){}
}edge[MAXN<<1];
il add_edge(int u,int v){
	edge[++num_edge]=Edge(head[u],v),head[u]=num_edge;
	edge[++num_edge]=Edge(head[v],u),head[v]=num_edge;
}
il DFS(int u,int fa){
	dp[u][c[u]]++,dp[u][1]++;
	for(ri i=head[u];i;i=edge[i].next){
		if(edge[i].to==fa) continue;
		DFS(edge[i].to,u),del(tmp,0);
		for(ri j=1;j<p;++j)
			for(ri k=1;k<p;++k)
				tmp[j*k%p]=add(tmp[j*k%p],mul(dp[edge[i].to][j],dp[u][k],mod));
		for(ri j=1;j<p;++j) dp[u][j]=tmp[j];
	}
}
int main()
{
	freopen("tree.in","r",stdin);
	freopen("tree.out","w",stdout);
	read(n),read(p);
	for(ri i=1;i<n;++i) read(u),read(v),add_edge(u,v);
	for(ri i=1;i<=n;++i) read(c[i]),c[i]%=p;
	for(ri i=1;i<=n;++i) read(b[i]),b[i]%=p;
	DFS(1,0);
	for(ri i=1;i<=n;++i) print(dp[i][b[i]]),putchar(' ');
	return 0;
}

总结

就一个子：出题人真滴毒瘤！！！