T20200924

Posted on Edited on In Word count in article: 2.2k Reading time ≈ 8 mins.
大东辰的测试

T1(吃屎题)

这个题，当时交错文件了，真该吃屎

就是说，当前的字符作为开头是否是一个更优的选择

如果是，那么就可以清空字符

否则，找到最优的位置插进去

就是一裸的贪心

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
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 1e7 + 10;
const int mod = 1e9 + 7;

int len, cnt;
char temp[maxn];
char ans[maxn], opt[maxn];

inline int Find(char x)
{
    int l(0), r(cnt), rp(cnt);
    if (x <= ans[cnt - 1]) return rp;
    ans[cnt] = 'a';
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (ans[mid] < x) rp = mid, r = mid - 1;
        else l = mid + 1;
    }
    return rp;
}

signed main()
{
    scanf ("%d %s", &len, temp);
    for (int i(0); i < len; ++i) {
        if (ans[0] >= temp[i]) {
            int p = Find(temp[i]);
            ans[cnt = p] = temp[i];
            ++cnt; 
        }
        else {
            cnt = 0;
            ans[cnt] = temp[i];
            cnt++;
        }
    }
    for (int i = 0; i < cnt; ++i) putchar(ans[i]);
}

T2(掉分提)

首先考虑\(1\)的代价

  • 我们要删除\(1\)，无论\(1\)在哪里，他的最优决策一定是用\(1\)的代价删除
  • 然后，忽略数列中的所有\(1\)，它就可以看作是一的\(k\)段的数列

那么现在得到的就是\(k\)段不含\(1\)的数列，假设它为\(a,b,c,d,e,f\cdots z\)

然后我们假设现在通过最优策略进行删除操作，那么得到了这样一个东西：

  • \(x(p_1),y,z(p_2)\)
  • \(x\)表示\(y\)的左边最小的数，得到他的代价为\(p_1\)
  • \(z\)表示\(y\)的右边最小的数，得到他的代价为\(p_2\)

那么合并\(x,y,z\)的方案就有两种：

  • 先合并中间的\(y\)，总花费为：\(cost=xyz+xz+\min(x,z)\)
  • 县合并两边，总花费为：\(cost=xy+yz+min(x,y,z)\)

显然，\(\min(x,y,z)\le\min(x,z)\)，且\(y(x+z)\le yxz\)

所以可以证明，从每一段的两边开始取的答案一定最优

那么每一小段答案就可以记作

\[ ans=\sum_{i=2}^nai*a_{i-1}+\min_{i=1}^na_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
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 5e6 + 10;
const int mod = 1e9 + 7;

inline int __read()
{
    int x(0), t(1);
    char o (getchar());
    while (o < '0' || o > '9') {
        if (o == '-') t = -1;
        o = getchar();
    }
    for (; o >= '0' && o <= '9'; o = getchar()) {
        x = (x << 1) + (x << 3) + (o ^ 48);
    }
    return x * t;
}

ll a, b, minx, ans;

signed main()
{
    freopen ("b.in", "r", stdin);
    freopen ("b.out", "w", stdout);
    int n = __read();
    for (int i = 1; i <= n; ++i) {
        b = __read();
        if (b == 1) {
            ans += 1;
            a = b = 0;
            ans += minx;
            minx = 0;
            continue;
        }
        ans += a * b;
        a = b;
        if (!minx || a < minx) minx = a;
    };
    cout << ans + minx << endl;
}

T3(爆零题)

就是说，可以把从\(S\rightarrow T\)的某条最短路上的边权改成\(0\)

然后问\(X\rightarrow Y\)的最短路径长度为多少

这道题是被欧歌爆砍\(100\)的

于是呢，我也是按照欧歌的改的

从\(X\rightarrow Y\)的路径长度，首先可以直接跑最短路

怎么处理\(S\rightarrow T\)的最短路边权为\(0\)呢？

看张图：

q.png

嗯，感觉就挺显然的了，就是看再\(S\rightarrow T\)的最短路径上的点到\(X\rightarrow Y\)的最短路径之和

就跑\(3\)次最短路即可

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
#include<bits/stdc++.h>
#define ll long long
#define mid (l+r)/2
using namespace std;
const ll INF=0x3f3f3f3f3f3f3f3f;
const int MOD=1e9+7;
const int N=5e6+7;
int n,m,s,t,x,y;
struct Edge{
	int e,next;
	ll w;
}edge[N<<1];
int head[N],cnt;
void add(int s,int e,int w)
{
	edge[++cnt].e=e;
	edge[cnt].w=w;
	edge[cnt].next=head[s];
	head[s]=cnt;
}
deque<int> q;
bool vis[N];
ll diss[N],dist[N],disy[N],disx[N];
ll Minx[N],Miny[N],ans=INF;
void SPFA(int start,ll dis[])
{
	dis[start]=0;q.push_front(start);
	vis[start]=1;
	while(!q.empty())
	{
		int now=q.front();
		q.pop_front();
		vis[now]=0;
		for(int i=head[now];i;i=edge[i].next)
		{
			int to=edge[i].e;
			if(dis[to]>dis[now]+edge[i].w)
			{
				dis[to]=dis[now]+edge[i].w;
				if(!vis[to])
				{
					if(q.empty()||dis[q.front()]>dis[to]) q.push_front(to);
					else q.push_back(to);
					vis[to]=1;
				}
			}
		}
	}
	return ;
}
void dfs(int now,int from,ll d1,ll d2)
{
	d1=min(d1,disx[now]);
	d2=min(d2,disy[now]);
	ans=min(ans,d1+d2);
	for(int i=head[now];i;i=edge[i].next)
	{
		int to=edge[i].e;
		if(diss[now]==diss[to]+edge[i].w)
			dfs(to,now,d1,d2);
	}
	return ;
}
int main()
{
	scanf("%d%d",&n,&m);
	scanf("%d%d",&s,&t);
	scanf("%d%d",&x,&y);
	for(int i=1;i<=m;++i)
	{
		int u,v;ll w;
		scanf("%d%d%lld",&u,&v,&w);
		add(u,v,w);
		add(v,u,w);
	}
	memset(diss,0x3f,sizeof(diss));
	memset(disx,0x3f,sizeof(disx));
	memset(disy,0x3f,sizeof(disy));
	SPFA(s,diss);
	SPFA(x,disx);
	SPFA(y,disy);
	dfs(t,0,INF,INF);
	ans=min(ans,disx[y]);
	printf("%lld",ans);
	return 0;
}

欧歌牛逼！！！

T4(退役题)

这，先贴一个\(STD\)，有题解的时候再回来看看吧

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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
#include <bits/stdc++.h>

using namespace std;

#define ge getchar()
#define Re read()

inline int read() {
	int x = 0, ch;
	while(!isdigit(ch = ge)) ;
	while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = ge;
	return x;
}

const int Base[] = {1, 5, 15, 30, 60, 120, 240};
const int mod = 1004535809;

int n;
int cnt[500];

template<typename T> inline T Mod(T x) { return x < 0 ? (x % mod + mod) : (x < mod ? x : (x < (mod << 1) ? x - mod : x % mod)); }
template<typename T> inline void Add(T&x, T y) { x = Mod(x + y); }

int tot;
int pri[500];
int chk[500];
int Min[500];
int pw[310000];
int fac[500];
int inv[500];
int ifac[500];

inline void init(int mx) {
	for(int i = 2; i <= mx; i++) {
		if(!chk[i]) pri[++tot] = i, Min[i] = i;
		for(int j = 1; j <= tot; j++) {
			if(i * pri[j] > mx) break;
			chk[i * pri[j]] = 1;
			Min[i * pri[j]] = pri[j];
			if(i % pri[j] == 0) break;
		}
	}
	pw[0] = fac[0] = fac[1] = inv[0] = inv[1] = ifac[0] = ifac[1] = 1;
	for(int i = 1; i <= 300000; i++) pw[i] = Mod(pw[i - 1] << 1);
	for(int i = 2; i <= mx; i++) {
		fac[i] = Mod(1LL * fac[i - 1] * i);
		inv[i] = Mod(1LL * (mod - mod / i) * inv[mod % i]);
		ifac[i] = Mod(1LL * ifac[i - 1] * inv[i]);
	}
}

struct Node {
	int a[7];

	Node() { memset(a, 0, sizeof(a)); }

	inline void init(int v) {
		while(!(v & 1)) ++a[0], v >>= 1;
		while(v % 3 == 0) ++a[1], v /= 3;
		while(v % 5 == 0) ++a[2], v /= 5;
		while(v % 7 == 0) ++a[3], v /= 7;
		while(v % 11 == 0) ++a[4], v /= 11;
		while(v % 13 == 0) ++a[5], v /= 13;
		while(v % 17 == 0) ++a[6], v /= 17;
	}

	inline void unlock(int v) {
		for(int i = 0; i < 6; i++)
			a[i] = v % Base[i + 1] / Base[i];
		a[6] = v / Base[6];
	}

	inline void Merge(Node x) {
		for(int i = 0; i < 7; i++)
			a[i] = max(a[i], x.a[i]);
	}

	inline int val() {
		int res = 0;
		for(int i = 0; i < 7; i++)
			res += a[i] * Base[i];
		return res;
	}
}Num[310];

int f[500][500];
int g[500][500];
int h[500][500];
int G[9][6][4][3][3][3][3];
int vis[500];
int nu[500][500];
int mx[500][500];
int ct[500];
int sum[500];
int Pw[500][500];

inline int solve(int p, Node x) {
	int v = x.val();
	if(g[p][v]) return f[p][v];
	g[p][v] = 1; int&F = f[p][v];
	if(p == 7) {
		for(int a0 = 0; a0 < 9; ++a0)
		for(int a1 = 0; a1 < 6; ++a1)
		for(int a2 = 0; a2 < 4; ++a2)
		for(int a3 = 0; a3 < 3; ++a3)
		for(int a4 = 0; a4 < 3; ++a4)
		for(int a5 = 0; a5 < 3; ++a5)
		for(int a6 = 0; a6 < 3; ++a6) {
			if(!G[a0][a1][a2][a3][a4][a5][a6]) continue;
			int Prd = 1;
			Prd = Mod(1LL * Prd * Pw[0][max(a0, x.a[0])]);
			Prd = Mod(1LL * Prd * Pw[1][max(a1, x.a[1])]);
			Prd = Mod(1LL * Prd * Pw[2][max(a2, x.a[2])]);
			Prd = Mod(1LL * Prd * Pw[3][max(a3, x.a[3])]);
			Prd = Mod(1LL * Prd * Pw[4][max(a4, x.a[4])]);
			Prd = Mod(1LL * Prd * Pw[5][max(a5, x.a[5])]);
			Prd = Mod(1LL * Prd * Pw[6][max(a6, x.a[6])]);
			F = Mod(F + 1LL * G[a0][a1][a2][a3][a4][a5][a6] * Prd);
		} return F;
	} F = solve(p - 1, x); Node now, sta;
	for(int a0 = 0; a0 <= mx[p][0]; ++a0)
	for(int a1 = 0; a1 <= mx[p][1]; ++a1)
	for(int a2 = 0; a2 <= mx[p][2]; ++a2)
	for(int a3 = 0; a3 <= mx[p][3]; ++a3)
	for(int a4 = 0; a4 <= mx[p][4]; ++a4)
	for(int a5 = 0; a5 <= mx[p][5]; ++a5)
	for(int a6 = 0; a6 <= mx[p][6]; ++a6) {
		sta.a[0] = a0, sta.a[1] = a1, sta.a[2] = a2;
		sta.a[3] = a3, sta.a[4] = a4, sta.a[5] = a5;
		sta.a[6] = a6;
		if(!h[p][sta.val()]) continue;
		now = x, now.Merge(sta);
		F = Mod(F + 1LL * h[p][sta.val()] * solve(p - 1, now));
	} return F;
}

int main() {
	freopen("d.in", "r", stdin);
	freopen("d.out", "w", stdout);
	n = Re; init(300);
	for(int i = 1; i <= n; ++i) ++cnt[Re];
	for(int i = 1; i <= 300; i++) Num[i].init(i);
	Pw[0][0] = Pw[1][0] = Pw[2][0] = Pw[3][0] = Pw[4][0] = Pw[5][0] = Pw[6][0] = 1;
	for(int i = 1; i < 10; i++) {
		Pw[0][i] = Mod(2LL * Pw[0][i - 1]);
		Pw[1][i] = Mod(3LL * Pw[1][i - 1]);
		Pw[2][i] = Mod(5LL * Pw[2][i - 1]);
		Pw[3][i] = Mod(7LL * Pw[3][i - 1]);
		Pw[4][i] = Mod(11LL * Pw[4][i - 1]);
		Pw[5][i] = Mod(13LL * Pw[5][i - 1]);
		Pw[6][i] = Mod(17LL * Pw[6][i - 1]);
	}
	for(int i = 8; i <= tot; i++) {
		h[i][0] = 1;
		for(int j = 0; j < 7; j++) {
			int p = pri[j + 1], prd = pri[i];
			while(prd * p <= 300) ++mx[i][j], prd *= p;
		}
		for(int j = pri[i]; j <= 300; j += pri[i]) {
			int Prd = pw[cnt[j]] - 1;
			if(!Prd) continue;
			vis[j] = 1; Node sta, tmp;
			for(int s = 479; ~s; s--) {
				if(!h[i][s]) continue;
				sta.unlock(s), sta.Merge(Num[j]);
				Add(h[i][sta.val()], int(Mod(1LL * h[i][s] * Prd)));
				sta = tmp;
			}
		} --h[i][0];
		for(int s = 0; s < 480; s++)
			h[i][s] = Mod(1LL * h[i][s] * pri[i]);
	}
	G[0][0][0][0][0][0][0] = 1;
	for(int i = 1; i <= 300; i++) {
		if(!vis[i]) {
			int Prd = pw[cnt[i]] - 1;
			if(!Prd) continue;
			Node sta; sta = Num[i];
			for(int a0 = 8; ~a0; --a0)
			for(int a1 = 5; ~a1; --a1)
			for(int a2 = 3; ~a2; --a2)
			for(int a3 = 2; ~a3; --a3)
			for(int a4 = 2; ~a4; --a4)
			for(int a5 = 2; ~a5; --a5)
			for(int a6 = 2; ~a6; --a6) {
				int A0 = max(a0, sta.a[0]);
				int A1 = max(a1, sta.a[1]);
				int A2 = max(a2, sta.a[2]);
				int A3 = max(a3, sta.a[3]);
				int A4 = max(a4, sta.a[4]);
				int A5 = max(a5, sta.a[5]);
				int A6 = max(a6, sta.a[6]);
				Add(G[A0][A1][A2][A3][A4][A5][A6], int(Mod(1LL * Prd * G[a0][a1][a2][a3][a4][a5][a6])));
			}
		}
	}
	printf("%d\n", solve(tot, Num[1]));
	return 0;
}

代码不长，也就\(200\)行，溜了溜了

鸽着的啊~