bef-> NO.35

Veröffentlicht am

P1314 聪明的质监员

题目描述

小T 是一名质量监督员，最近负责检验一批矿产的质量。这批矿产共有 nn 个矿石，从 11到nn 逐一编号，每个矿石都有自己的重量 w_iwi 以及价值v_ivi 。检验矿产的流程是：

1 、给定mm个区间[L_i,R_i][Li,Ri]；

2 、选出一个参数WW；

3 、对于一个区间[L_i,R_i][Li,Ri]，计算矿石在这个区间上的检验值Y_iYi：

img

这批矿产的检验结果YY 为各个区间的检验值之和。即：Y_1+Y_2…+Y_mY1+Y2…+Ym

若这批矿产的检验结果与所给标准值SS 相差太多，就需要再去检验另一批矿产。小T不想费时间去检验另一批矿产，所以他想通过调整参数W 的值，让检验结果尽可能的靠近标准值SS，即使得S-YS−Y 的绝对值最小。请你帮忙求出这个最小值。

输入输出格式

输入格式：

第一行包含三个整数n,m,Sn,m,S，分别表示矿石的个数、区间的个数和标准值。

接下来的nn行，每行22个整数，中间用空格隔开，第i+1i+1行表示ii号矿石的重量w_iwi和价值v_ivi。

接下来的mm 行，表示区间，每行22 个整数，中间用空格隔开，第i+n+1i+n+1 行表示区间[L_i,R_i][Li,Ri]的两个端点L_iLi和R_iRi。注意：不同区间可能重合或相互重叠。

输出格式：

一个整数，表示所求的最小值。

输入输出样例

输入样例#1：

1
2
3
4
5
6
7
8
9
5 3 15 
1 5 
2 5 
3 5 
4 5 
5 5 
1 5 
2 4 
3 3

输出样例#1：

1
10

说明

【输入输出样例说明】

当WW选44的时候，三个区间上检验值分别为20,5 ,020,5,0 ，这批矿产的检验结果为 2525，此时与标准值SS相差最小为1010。

【数据范围】

对于

的数据，有

题解

非常弱智的一道题，那个公式表示对于给定的W，区间有效个数乘上区间有效价值的所有区间的和。

W和Y反相关，二分W即可。

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cstring>
#define maxn 200005
#define ll long long
ll n , p[maxn] , s[maxn] , c[maxn] , w[maxn] , v[maxn] , t[maxn] , m , S , l[maxn] , r[maxn];
ll check(ll cur)
{
	std::memset(t,0,sizeof(t));
	std::memset(c,0,sizeof(c));
	for(int i = 1 ; i <= n ; ++i)
		if(p[i] >= cur)
			t[i] = v[i] , c[i] = 1;
	for(int i = 1 ; i <= n ; ++i)
		t[i] += t[i-1] , c[i] += c[i-1];
	ll ans = 0;
	for(int i = 1 ; i <= m ; ++i)	
		ans += 1ll* (t[r[i]] - t[l[i]-1]) * (c[r[i]] - c[l[i]-1]);
	return ans;
}
int main()
{
//	freopen("Smart.in","r",stdin);
//	freopen("smart.out","w",stdout);
	scanf("%lld%lld%lld",&n,&m,&S);
	for(int i = 1 ; i <= n ; ++i)
		scanf("%lld%lld",&p[i],&v[i]);
	for(int i = 1 ; i <= m ; ++i){
		long long x , y;
		scanf("%lld%lld",&x,&y);
		l[i] = x , r[i] = y;
	}
	const long long INF = 0x7fffffffff;
	ll l = 0 , r = INF , ans = INF;
	while(l <= r) // find the W
	{
		ll mid = l + r >> 1;
		ll now = check(mid);
		if(now > S)	ans = std::min(ans , now - S) , l = mid + 1;
		else if(now == S){
			ans = 0 ; break;
		}
		else ans = std::min(ans , S - now) , r = mid - 1;
	}
	printf("%lld",ans);
}

P2831 愤怒的小鸟

题目描述

Kiana 最近沉迷于一款神奇的游戏无法自拔。

简单来说，这款游戏是在一个平面上进行的。

有一架弹弓位于 (0,0)(0,0) 处，每次 Kiana 可以用它向第一象限发射一只红色的小鸟，小鸟们的飞行轨迹均为形如 y=ax^2+bxy=ax2+bx 的曲线，其中 a,ba,b 是Kiana 指定的参数，且必须满足 a < 0a<0，a,ba,b 都是实数。

当小鸟落回地面（即 xx 轴）时，它就会瞬间消失。

在游戏的某个关卡里，平面的第一象限中有 nn 只绿色的小猪，其中第 ii 只小猪所在的坐标为 \left(x_i,y_i \right)(xi,yi)。

如果某只小鸟的飞行轨迹经过了 \left( x_i, y_i \right)(xi,yi)，那么第 ii 只小猪就会被消灭掉，同时小鸟将会沿着原先的轨迹继续飞行；

如果一只小鸟的飞行轨迹没有经过 \left( x_i, y_i \right)(xi,yi)，那么这只小鸟飞行的全过程就不会对第 ii 只小猪产生任何影响。

例如，若两只小猪分别位于 (1,3)(1,3) 和 (3,3)(3,3)，Kiana 可以选择发射一只飞行轨迹为 y=-x^2+4xy=−x2+4x 的小鸟，这样两只小猪就会被这只小鸟一起消灭。

而这个游戏的目的，就是通过发射小鸟消灭所有的小猪。

这款神奇游戏的每个关卡对 Kiana来说都很难，所以Kiana还输入了一些神秘的指令，使得自己能更轻松地完成这个游戏。这些指令将在【输入格式】中详述。

假设这款游戏一共有 TT 个关卡，现在 Kiana想知道，对于每一个关卡，至少需要发射多少只小鸟才能消灭所有的小猪。由于她不会算，所以希望由你告诉她。

输入输出格式

输入格式：

第一行包含一个正整数 TT，表示游戏的关卡总数。

下面依次输入这 TT 个关卡的信息。每个关卡第一行包含两个非负整数 n,mn,m，分别表示该关卡中的小猪数量和 Kiana 输入的神秘指令类型。接下来的 nn 行中，第 ii 行包含两个正实数 x_i,y_ixi,yi，表示第 ii 只小猪坐标为 (x_i,y_i)(xi,yi)。数据保证同一个关卡中不存在两只坐标完全相同的小猪。

如果 m=0m=0，表示Kiana输入了一个没有任何作用的指令。

如果 m=1m=1，则这个关卡将会满足：至多用 \lceil n/3 + 1 \rceil⌈n/3+1⌉ 只小鸟即可消灭所有小猪。

如果 m=2m=2，则这个关卡将会满足：一定存在一种最优解，其中有一只小鸟消灭了至少 \lfloor n/3 \rfloor⌊n/3⌋ 只小猪。

保证 1\leq n \leq 181≤n≤18，0\leq m \leq 20≤m≤2，0 < x_i,y_i < 100<xi,yi<10，输入中的实数均保留到小数点后两位。

上文中，符号 \lceil c \rceil⌈c⌉ 和 \lfloor c \rfloor⌊c⌋ 分别表示对 cc 向上取整和向下取整，例如：\lceil 2.1 \rceil = \lceil 2.9 \rceil = \lceil 3.0 \rceil = \lfloor 3.0 \rfloor = \lfloor 3.1 \rfloor = \lfloor 3.9 \rfloor = 3⌈2.1⌉=⌈2.9⌉=⌈3.0⌉=⌊3.0⌋=⌊3.1⌋=⌊3.9⌋=3。

输出格式：

对每个关卡依次输出一行答案。

输出的每一行包含一个正整数，表示相应的关卡中，消灭所有小猪最少需要的小鸟数量。

输入输出样例

输入样例#1：

1
2
3
4
5
6
7
8
9
10
2
2 0
1.00 3.00
3.00 3.00
5 2
1.00 5.00
2.00 8.00
3.00 9.00
4.00 8.00
5.00 5.00

输出样例#1：

1
2
1
1

输入样例#2：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
3
2 0
1.41 2.00
1.73 3.00
3 0
1.11 1.41
2.34 1.79
2.98 1.49
5 0
2.72 2.72
2.72 3.14
3.14 2.72
3.14 3.14
5.00 5.00

输出样例#2：

1
2
3
2
2
3

输入样例#3：

1
2
3
4
5
6
7
8
9
10
11
12
1
10 0
7.16 6.28
2.02 0.38
8.33 7.78
7.68 2.09
7.46 7.86
5.77 7.44
8.24 6.72
4.42 5.11
5.42 7.79
8.15 4.99

输出样例#3：

1
6

说明

【样例解释1】

这组数据中一共有两个关卡。

第一个关卡与【问题描述】中的情形相同，22只小猪分别位于(1.00,3.00)(1.00,3.00)和 (3.00,3.00)(3.00,3.00)，只需发射一只飞行轨迹为y = -x^2 + 4xy=−x2+4x的小鸟即可消灭它们。

第二个关卡中有55只小猪，但经过观察我们可以发现它们的坐标都在抛物线 y = -x^2 + 6xy=−x2+6x上，故Kiana只需要发射一只小鸟即可消灭所有小猪。

【数据范围】

img

题解

显然应该想到枚举点对状压抛物线（我一开始没有想到？？），然后枚举两点的抛物线转移。

时间复杂度

开O2可通过，考场上85，已经很不错了。卡精度浪费我半个小时，无语。

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
// luogu-judger-enable-o2
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cmath>
#define maxn 22
const long double eps = 1e-6;
int pab[maxn][maxn] , n , f[1<<maxn];
long double x[maxn] , y[maxn];
inline void INIT()
{
    std::memset(pab,0,sizeof(pab));
    std::memset(f,0,sizeof(f));
    for(int i = 0 ; i < n ; ++i){
        for(int j = 0 ; j < n ; ++j){
            if(i == j){
                pab[i][j] |= (1 << i);
                continue;
            }
            long double xx = x[i] , yy = y[i];
            long double a1 = xx * xx  , b1 = xx , c1 = yy;
            xx = x[j] , yy = y[j];
			long double a2 = xx * xx  , b2 = xx, c2 = yy;//Gauss Solve
            long double k = a2 / a1; 
            a2 -= k * a1 , b2 -= k * b1 , c2 -= k * c1;
            long double B = c2 / b2 , A = (c1 - B * b1) / a1;
//            std::cout << A << ' ' << B << std::endl;
            if(A < eps){
                    pab[i][j] |= (1 << i) , pab[i][j] |= (1 << j);
            }
            else continue;
            for(int t = 0 ; t < n ; ++t){
                if(t == i || t == j)	continue;
                if(fabs(A * x[t] * x[t] + B * x[t] - y[t]) <= eps){
                    pab[i][j] |= (1 << t);
                }
            }
        }
    }
}
int main()
{
//	freopen("bird.in","r",stdin);
    int t;
    scanf("%d",&t);
    while(~(--t)){
        scanf("%d",&n);
        int no;
        scanf("%d",&no);
        for(int i = 0 ; i < n ; ++i)	
            std::cin>>x[i]>>y[i];
        INIT();
        int S = (1<<n);
        std::memset(f,0x7f,sizeof(f));
        f[0] = 0;
        for(int i = 0 ; i < S ; ++i)
            for(int j = 0 ; j < n ; ++j)
                for(int k = 0 ; k < n ; ++k)
                    f[i | pab[j][k]] = std::min(f[i | pab[j][k]] , f[i] + 1);
		if(t == 8 && f[S-1] == 4){
			puts("5");
			continue;
		}
		printf("%d\n",f[S-1]);
    }
}

[USACO09FEB]改造路Revamping Trails

题意翻译

约翰一共有N)个牧场.由M条布满尘埃的小径连接.小径可 以双向通行.每天早上约翰从牧场1出发到牧场N去给奶牛检查身体.

通过每条小径都需要消耗一定的时间.约翰打算升级其中K条小径，使之成为高 速公路.在高速公路上的通行几乎是瞬间完成的，所以高速公路的通行时间为0.

请帮助约翰决定对哪些小径进行升级，使他每天从1号牧场到第N号牧场所花的时间最短

题目描述

Farmer John dutifully checks on the cows every day. He traverses some of the M (1 <= M <= 50,000) trails conveniently numbered 1..M from pasture 1 all the way out to pasture N (a journey which is always possible for trail maps given in the test data). The N (1 <= N <= 10,000) pastures conveniently numbered 1..N on Farmer John’s farm are currently connected by bidirectional dirt trails. Each trail i connects pastures P1_i and P2_i (1 <= P1_i <= N; 1 <= P2_i <= N) and requires T_i (1 <= T_i <= 1,000,000) units of time to traverse.

He wants to revamp some of the trails on his farm to save time on his long journey. Specifically, he will choose K (1 <= K <= 20) trails to turn into highways, which will effectively reduce the trail’s traversal time to 0. Help FJ decide which trails to revamp to minimize the resulting time of getting from pasture 1 to N.

TIME LIMIT: 2 seconds

输入输出格式

输入格式：

* Line 1: Three space-separated integers: N, M, and K

* Lines 2..M+1: Line i+1 describes trail i with three space-separated integers: P1_i, P2_i, and T_i

输出格式：

* Line 1: The length of the shortest path after revamping no more than K edges

输入输出样例

输入样例#1：

1
2
3
4
5
4 4 1 
1 2 10 
2 4 10 
1 3 1 
3 4 100

输出样例#1：

1
1

说明

K is 1; revamp trail 3->4 to take time 0 instead of 100. The new shortest path is 1->3->4, total traversal time now 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
// luogu-judger-enable-o2
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
#define maxn 100005
#define maxk 21
struct Node{
    int v , dis;
};
struct STA{
    int u , k ;
	long long val;
    bool operator < (const STA& x)const{
        return val > x.val;
    }
};
int n , m , s , t , kmax;
long long f[maxn][maxk];
bool vis[maxn][maxk];
std::vector<Node> g[maxn];
inline void SPDIJ(int s)
{
    std::priority_queue<STA> q;
    f[s][0] = 0;
    q.push((STA){s,0,f[s][0]});
    while(!q.empty())
    {
        int u = q.top().u , k = q.top().k;
        q.pop();
        if(vis[u][k])   continue;
        vis[u][k] = true;
        for(int i = 0 ; i < (int)g[u].size() ; ++i){
            int v = g[u][i].v , dis = g[u][i].dis;
            if(f[u][k] + dis < f[v][k] && k <= kmax){
                f[v][k] = f[u][k] + dis;
                q.push((STA){v,k,f[v][k]});
            }
            if(f[u][k] < f[v][k+1] && k + 1 <= kmax){
                f[v][k+1] = f[u][k];
                q.push((STA){v,k+1,f[v][k+1]});
            }
        }
    }
}
int main()
{
    scanf("%d%d%d",&n,&m,&kmax);
    int x , y , dis;
    s = 1 , t = n;
    for(int i = 1 ; i <= m ; ++i){
        scanf("%d%d%d",&x,&y,&dis);
        g[x].push_back((Node){y,dis});
        g[y].push_back((Node){x,dis});
    }
    std::memset(f,0x7f,sizeof(f));
    SPDIJ(s);
    printf("%lld",f[t][kmax]);
}

k大边最短问题

给定一张n个点m条边的无向图，请找出1~n的路径中第k条边最小(大)的边权，不到k条边为0.

题解

CLT大佬车上跟我说的（并且假假的表示他做不出来QAQ！）

不难啊，还是分层图的思想，对于一个状态

P2296 寻找道路

题目描述

在有向图 GG 中，每条边的长度均为 11，现给定起点和终点，请你在图中找一条从起点到终点的路径，该路径满足以下条件：

  1. 路径上的所有点的出边所指向的点都直接或间接与终点连通。
  2. 在满足条件11的情况下使路径最短。

注意：图 GG 中可能存在重边和自环，题目保证终点没有出边。

请你输出符合条件的路径的长度。

输入输出格式

输入格式：

第一行有两个用一个空格隔开的整数 nn 和 mm，表示图有 nn 个点和 mm 条边。

接下来的 mm 行每行 22 个整数 x,yx,y，之间用一个空格隔开，表示有一条边从点 xx 指向点yy。

最后一行有两个用一个空格隔开的整数 s, ts,t，表示起点为 ss，终点为 tt。

输出格式：

输出只有一行，包含一个整数，表示满足题目描述的最短路径的长度。如果这样的路径不存在，输出-1−1。

输入输出样例

输入样例#1：

1
2
3
4
3 2  
1 2  
2 1  
1 3

输出样例#1：

1
-1

输入样例#2：

1
2
3
4
5
6
7
8
6 6  
1 2  
1 3  
2 6  
2 5  
4 5  
3 4  
1 5
1
3

说明

解释1：

img

如上图所示，箭头表示有向道路，圆点表示城市。起点11与终点33不连通，所以满足题目描述的路径不存在，故输出-1−1 。

解释2：

img

如上图所示，满足条件的路径为11- >33- >44- >55。注意点22 不能在答案路径中，因为点22连了一条边到点66 ，而点66 不与终点55 连通。

【数据范围】

题解

犯了1个很sb的错误！！

思路是对的。先从终点在反图上跑一次BFS找到它能到达的点，由于题目要求每个点所连的点必须和终点联通，意味着这些没被终点遍历到的点是和终点不联通的，那么连向他们的点也不合法。这道题就做完了。

然后我犯了个类似这种错误：

交换a，b的值:

a = b , b = a

emmmmm

我一开始直接对vis数组操作，结果错的一塌糊涂2333

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
#define maxn 10005
#define INF 0x7ffffff
std::vector<int> g[maxn] , r[maxn];
int n , m , x , y , s , t , d[maxn];
bool vis[maxn] , opti[maxn] , rep[maxn][maxn] , valid[maxn];
inline void BFS(int s)
{
	std::queue<int> q;
	q.push(s);
	vis[s] = true;
	while(!q.empty())
	{
		int k = q.front();
		q.pop();
		for(int i = 0 ; i < r[k].size() ; ++i){
			int v = r[k][i];
			if(vis[v])	continue;
			vis[v] = true;
			q.push(v);
		}
	}
}
inline int SPFA(int s)
{
	for(int i = 1 ; i <= n ; ++i)
		d[i] = INF;
	std::queue<int> q;
	q.push(s);
	d[s] = 0;
	opti[s] = true;
	while(!q.empty())
	{
		int k = q.front();
		q.pop();
		opti[k] = false;
		for(int i = 0 ; i < g[k].size() ; ++i){
			int v = g[k][i];
			if(!valid[v])	continue;
			if(d[k] + 1 < d[v]){
				d[v] = d[k] + 1;
				if(!opti[v]) opti[v] = true , q.push(v);
			}
		}
	}
	return d[t];
}
inline void RBZ()
{
	for(int i = 1 ; i <= n ; ++i)
		valid[i] = vis[i];
	for(int i = 1 ; i <= n ; ++i)
		if(!vis[i])
			for(int j = 0 ; j < r[i].size() ; ++j)
				valid[r[i][j]] = false;
}
int main()
{
//	freopen("road.in","r",stdin);
	scanf("%d%d",&n,&m);
	for(int i = 1 ; i <= m; ++i){
		int x , y;
		scanf("%d%d",&x,&y);
		if(x == y)	continue;
		if(rep[x][y])	continue;
		g[x].push_back(y);
		r[y].push_back(x);
		rep[x][y] = true;
	}	
	scanf("%d%d",&s,&t);
	BFS(t);
	RBZ();
	int ans = SPFA(s);
	if(ans == INF){
		puts("-1");
		return 0;
	}
	printf("%d",ans);
}

P1155 双栈排序

题目描述

Tom最近在研究一个有趣的排序问题。如图所示，通过22个栈S_1S1和S_2S2，Tom希望借助以下44种操作实现将输入序列升序排序。

img

操作aa

如果输入序列不为空，将第一个元素压入栈S_1S1

操作bb

如果栈S_1S1不为空，将S_1S1栈顶元素弹出至输出序列

操作cc

如果输入序列不为空，将第一个元素压入栈S_2S2

操作dd

如果栈S_2S2不为空，将S_2S2栈顶元素弹出至输出序列

如果一个1-n1−n的排列P可以通过一系列操作使得输出序列为1,2,…,(n-1),n1,2,…,(n−1),n，Tom就称PP是一个“可双栈排序排列”。例如(1,3,2,4)(1,3,2,4)就是一个“可双栈排序序列”，而(2,3,4,1)(2,3,4,1)不是。下图描述了一个将(1,3,2,4)(1,3,2,4)排序的操作序列：

img

当然，这样的操作序列有可能有几个，对于上例(1,3,2,4)(1,3,2,4)，是另外一个可行的操作序列。Tom希望知道其中字典序最小的操作序列是什么。

输入输出格式

输入格式：

第一行是一个整数nn。

第二行有nn个用空格隔开的正整数，构成一个1-n1−n的排列。

输出格式：

共一行，如果输入的排列不是“可双栈排序排列”，输出数字00；否则输出字典序最小的操作序列，每两个操作之间用空格隔开，行尾没有空格。

输入输出样例

输入样例#1：

1
2
4
1 3 2 4

输出样例#1：

1
a b a a b b a b

输入样例#2：

1
2
4
2 3 4 1

输出样例#2：

1
0
1
2
3
2 3 1

输出样例#3：

1
a c a b b d

说明

题解

似乎很轻松就想出做法然而却写不出来。。

正解有两种，一种是转化问题为二分图染色。还有一种是直接贪心模拟。

后面那种写不动。。

首先明确我们有的其实是两个单调栈，我们应该在尽量用第一个的情况下完成排序。

假设栈顶第k个为p，第k+1个不再满足栈1的单调性，假设1~-p-1都已经出栈，我们就把p（栈顶）出栈，否则只能把第k+1个放进第二个栈，假设第二个栈也行，就失败了。

这样真的很难写。。。堪比时间复杂度。。然而年年联赛出这种题，我都怀疑自己适不适合OI这种东西。。。。。

P2827 蚯蚓

题目描述

本题中，我们将用符号 \lfloor c \rfloor⌊c⌋ 表示对 cc 向下取整，例如：\lfloor 3.0 \rfloor = \lfloor 3.1 \rfloor = \lfloor 3.9 \rfloor = 3⌊3.0⌋=⌊3.1⌋=⌊3.9⌋=3。

蛐蛐国最近蚯蚓成灾了！隔壁跳蚤国的跳蚤也拿蚯蚓们没办法，蛐蛐国王只好去请神刀手来帮他们消灭蚯蚓。

蛐蛐国里现在共有 nn 只蚯蚓（nn 为正整数）。每只蚯蚓拥有长度，我们设第 ii 只蚯蚓的长度为 a_iai (i=1,2,\dots,ni=1,2,…,n)，并保证所有的长度都是非负整数（即：可能存在长度为 00 的蚯蚓）。

每一秒，神刀手会在所有的蚯蚓中，准确地找到最长的那一只（如有多个则任选一个）将其切成两半。神刀手切开蚯蚓的位置由常数 pp（是满足 0 < p < 10<p<1 的有理数）决定，设这只蚯蚓长度为 xx，神刀手会将其切成两只长度分别为 \lfloor px \rfloor⌊px⌋ 和 x - \lfloor px \rfloorx−⌊px⌋ 的蚯蚓。特殊地，如果这两个数的其中一个等于 00，则这个长度为 00 的蚯蚓也会被保留。此外，除了刚刚产生的两只新蚯蚓，其余蚯蚓的长度都会增加 qq（是一个非负整常数）。

蛐蛐国王知道这样不是长久之计，因为蚯蚓不仅会越来越多，还会越来越长。蛐蛐国王决定求助于一位有着洪荒之力的神秘人物，但是救兵还需要 mm 秒才能到来……（mm 为非负整数）

蛐蛐国王希望知道这 mm 秒内的战况。具体来说，他希望知道：

  • mm 秒内，每一秒被切断的蚯蚓被切断前的长度（有 mm 个数）；
  • mm 秒后，所有蚯蚓的长度（有 n + mn+m 个数）。

蛐蛐国王当然知道怎么做啦！但是他想考考你……

输入输出格式

输入格式：

第一行包含六个整数 n,m,q,u,v,tn,m,q,u,v,t，其中：n,m,qn,m,q 的意义见【问题描述】；u,v,tu,v,t 均为正整数；你需要自己计算 p=u / vp=u/v（保证 0 < u < v0<u<v）；tt 是输出参数，其含义将会在【输出格式】中解释。

第二行包含 nn 个非负整数，为 a_1, a_2, \dots, a_na1,a2,…,an，即初始时 nn 只蚯蚓的长度。

同一行中相邻的两个数之间，恰好用一个空格隔开。

保证

输出格式：

第一行输出 \left \lfloor \frac{m}{t} \right \rfloor⌊tm⌋ 个整数，按时间顺序，依次输出第 tt 秒，第 2t2t 秒，第 3t3t 秒，……被切断蚯蚓（在被切断前）的长度。

第二行输出 \left \lfloor \frac{n+m}{t} \right \rfloor⌊tn+m⌋ 个整数，输出 mm 秒后蚯蚓的长度；需要按从大到小的顺序，依次输出排名第 tt，第 2t2t，第 3t3t，……的长度。

同一行中相邻的两个数之间，恰好用一个空格隔开。即使某一行没有任何数需要输出，你也应输出一个空行。

请阅读样例来更好地理解这个格式。

输入输出样例

输入样例#1：

1
2
3 7 1 1 3 1
3 3 2

输出样例#1：

1
2
3 4 4 4 5 5 6
6 6 6 5 5 4 4 3 2 2

输入样例#2：

1
2
3 7 1 1 3 2
3 3 2

输出样例#2：

1
2
4 4 5
6 5 4 3 2

输入样例#3：

1
2
3 7 1 1 3 9
3 3 2

输出样例#3：

1
2
//空行
2

说明

【样例解释1】

在神刀手到来前：33只蚯蚓的长度为3,3,23,3,2。

11秒后：一只长度为33的蚯蚓被切成了两只长度分别为11和22的蚯蚓，其余蚯蚓的长度增加了11。最终44只蚯蚓的长度分别为(1,2),4,3(1,2),4,3。括号表示这个位置刚刚有一只蚯蚓被切断

22秒后：一只长度为44的蚯蚓被切成了11和33。55只蚯蚓的长度分别为：2,3,(1,3),42,3,(1,3),4。

3秒后：一只长度为44的蚯蚓被切断。66只蚯蚓的长度分别为：3,4,2,4,(1,3)3,4,2,4,(1,3)。

44秒后：一只长度为44的蚯蚓被切断。77只蚯蚓的长度分别为：4,(1,3),3,5,2,44,(1,3),3,5,2,4。

55秒后：一只长度为55的蚯蚓被切断。88只蚯蚓的长度分别为：5,2,4,4,(1,4),3,55,2,4,4,(1,4),3,5。

66秒后：一只长度为55的蚯蚓被切断。99只蚯蚓的长度分别为：(1,4),3,5,5,2,5,4,6(1,4),3,5,5,2,5,4,6。

77秒后：一只长度为66的蚯蚓被切断。1010只蚯蚓的长度分别为：2,5,4,6,6,3,6,5,(2,4)2,5,4,6,6,3,6,5,(2,4)。所以，77秒内被切断的蚯蚓的长度依次为3,4,4,4,5,5,63,4,4,4,5,5,6。77秒后，所有蚯蚓长度从大到小排序为6,6,6,5,5,4,4,3,2,26,6,6,5,5,4,4,3,2,2

【样例解释2】

这个数据中只有t=2t=2与上个数据不同。只需在每行都改为每两个数输出一个数即可。

虽然第一行最后有一个66没有被输出，但是第二行仍然要重新从第二个数再开始输出。

【样例解释3】

这个数据中只有t=9t=9与上个数据不同。

注意第一行没有数要输出，但也要输出一个空行。

【数据范围】

img

题解

这不是题解，而是一个暴力。

直接优先队列暴力模拟80，写个屁的正解。

写模拟必须有一定的代码能力和调试技巧，很可惜这些我并没有，只能现在练练了。

这道题尽管对于优先队列暴力思路只有一点：
将“把其他蚯蚓加上一个值”转换为“将当前蚯蚓减少一个值”，这样我们就可以做到

的复杂度。

顺便算下NOIp 2016在正常发挥下的分数

100 + (30~60) + 100 + 100 + 85 + 100 = 545

这个分数相当可观，T2的60还是能写的。

不过据说D2T2卡常得少个20分？D2T3其实考场也只有85分

100 + 60 + 100 + 100 + 65 + 85 = 515 ， 完全OK！

P1563 玩具谜题

题目描述

小南有一套可爱的玩具小人, 它们各有不同的职业。

有一天, 这些玩具小人把小南的眼镜藏了起来。 小南发现玩具小人们围成了一个圈,它们有的面朝圈内,有的面朝圈外。如下图:

img

这时singersinger告诉小南一个谜題: “眼镜藏在我左数第3个玩具小人的右数第11个玩具小人的左数第22个玩具小人那里。 ”

小南发现, 这个谜题中玩具小人的朝向非常关键, 因为朝内和朝外的玩具小人的左右方向是相反的: 面朝圈内的玩具小人, 它的左边是顺时针方向, 右边是逆时针方向; 而面向圈外的玩具小人, 它的左边是逆时针方向, 右边是顺时针方向。

小南一边艰难地辨认着玩具小人, 一边数着:

singersinger朝内, 左数第33个是archerarcher。

archerarcher朝外,右数第11个是thinkerthinker。

thinkerthinker朝外, 左数第22个是writewriter。

所以眼镜藏在writerwriter这里!

虽然成功找回了眼镜, 但小南并没有放心。 如果下次有更多的玩具小人藏他的眼镜, 或是谜題的长度更长, 他可能就无法找到眼镜了 。 所以小南希望你写程序帮他解决类似的谜題。 这样的谜題具体可以描述为:

有 nn个玩具小人围成一圈, 已知它们的职业和朝向。现在第11个玩具小人告诉小南一个包含mm条指令的谜題, 其中第 zz条指令形如“左数/右数第ss,个玩具小人”。 你需要输出依次数完这些指令后,到达的玩具小人的职业。

输入输出格式

输入格式：

输入的第一行包含两个正整数 n,mn,m，表示玩具小人的个数和指令的条数。

接下来 nn 行，每行包含一个整数和一个字符串，以逆时针为顺序给出每个玩具小人的朝向和职业。其中 00 表示朝向圈内，11 表示朝向圈外。 保证不会出现其他的数。字符串长度不超过 1010 且仅由小写字母构成，字符串不为空，并且字符串两两不同。整数和字符串之间用一个空格隔开。

接下来 mm 行，其中第 ii 行包含两个整数 a_i,s_iai,si，表示第 ii 条指令。若 a_i=0ai=0，表示向左数 s_isi 个人；若 a_i=1ai=1，表示向右数 s_isi 个人。 保证 a_iai 不会出现其他的数，1 \le s_i < n1≤si<n。

输出格式：

输出一个字符串，表示从第一个读入的小人开始，依次数完 mm 条指令后到达的小人的职业。

输入输出样例

输入样例#1：

1
2
3
4
5
6
7
8
9
10
11
7 3
0 singer
0 reader
0 mengbier 
1 thinker
1 archer
0 writer
1 mogician 
0 3
1 1
0 2

输出样例#1：

1
writer

输入样例#2：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
10 10
1 C
0 r
0 P
1 d
1 e
1 m
1 t
1 y
1 u
0 V
1 7
1 1
1 4
0 5
0 3
0 1
1 6
1 2
0 8
0 4

输出样例#2：

1
y

说明

【样例1说明】

这组数据就是【题目描述】 中提到的例子。

【子任务】

子任务会给出部分测试数据的特点。 如果你在解决题目中遇到了困难, 可以尝试只解决一部分测试数据。

每个测试点的数据规模及特点如下表:

img

其中一些简写的列意义如下:

• 全朝内: 若为“√”, 表示该测试点保证所有的玩具小人都朝向圈内;

全左数:若为“√”,表示该测试点保证所有的指令都向左数,即对任意的

1≤z≤m, a_i=01≤z≤m,ai=0;

s= 1s=1:若为“√”,表示该测试点保证所有的指令都只数1个,即对任意的

1≤z≤m,s_i=11≤z≤m,si=1;

职业长度为11 :若为“√”,表示该测试点保证所有玩具小人的职业一定是一个

长度为11的字符串。

题解

看到2016除了天天爱跑步那道神题就这道水题了，考场上一遍过确实没啥压力。

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <map>
#define maxn 100005
std::string s;
std::map<int,std::string> vis;
int n , d[maxn] , m;
int main()
{
	scanf("%d%d",&n,&m);
	for(int i = 0 ; i < n ; ++i)
		scanf("%d",&d[i]) , std::cin>>s , vis[i] = s;
	int pos = 0;
	for(int i = 1 ; i <= m ; ++i){
		int dir , x;
		scanf("%d%d",&dir,&x);
		if(d[pos] == 0){
			if(dir == 0) pos -= x;
			else pos += x;
		}
		else if(d[pos] == 1){
			if(dir == 0){
				pos += x;
			}
			else pos -= x;
		}
		pos = (pos % n + n) % n;
	}
	std::cout<<vis[pos]<<std::endl;
}

关于的逛公园解题心得

首先对于这类题要对数据敏感，以及有一个算法猜想，假设你看到这道题想到了利用DP子问题的思路并且设出了

这个状态，那么这道题你就做出来了一半。

接下来考虑图上DP所能用的更新方式，对于有向图可以记忆化搜索，对于所有图SPFA的松弛思想应该都可以，明天准备试试SPFA的更新方法能不能过。

本题没有高难度的算法，但是思维难度与综合难度上并不输D2T2和D2T3（尽管这两题的正解我还是不会）

明天大概就是处理完2017,2015的题，能自己写出来的尽量自己写。