秋刀鱼的博客
0%

发表于 分类于

题目链接：VJ(private)

扩展欧几里得定理

青蛙的约会

题目描述

两只青蛙在网上相识了，它们聊得很开心，于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上，于是它们约定各自朝西跳，直到碰面为止。可是它们出发之前忘记了一件很重要的事情，既没有问清楚对方的特征，也没有约定见面的具体位置。不过青蛙们都是很乐观的，它们觉得只要一直朝着某个方向跳下去，总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上，不然是永远都不可能碰面的。为了帮助这两只乐观的青蛙，你被要求写一个程序来判断这两只青蛙是否能够碰面，会在什么时候碰面。
我们把这两只青蛙分别叫做青蛙A和青蛙B，并且规定纬度线上东经0度处为原点，由东往西为正方向，单位长度1米，这样我们就得到了一条首尾相接的数轴。设青蛙A的出发点坐标是x，青蛙B的出发点坐标是y。青蛙A一次能跳m米，青蛙B一次能跳n米，两只青蛙跳一次所花费的时间相同。纬度线总长L米。现在要你求出它们跳了几次以后才会碰面。

输入

输入只包括一行5个整数x，y，m，n，L，其中x≠y < 2000000000，0 < m、n < 2000000000，0 < L < 2100000000。

输出

输出碰面所需要的跳跃次数，如果永远不可能碰面则输出一行”Impossible”

样例输入

1 2 3 4 5

样例输出

4

解释

可以列出同余方程 (x + m * t) % l = (y + n * t) % l，即(x + m * t) = (y + n * t) + k * l。移项得(x - y) + t * (m - n) = k * l。仿照二元一次不定方程的形式ax + by = c，我们可以得到l * k + (n - m) * t = x - y。
根据输入的数据，我们知道l, m, n, x, y这五个数，并且可以求出(n - m)和(x - y)。我们将l, (n - m), (x - y)代入扩展欧几里得算法， 得到k和t的一组解(x0 * (c / gcd(a, b)), y0 * (c / gcd(a, b)))。
方程无解的条件是c % gcd(a, b) != 0。如果满足方程无解的条件，输出”Impossible”。
否则，我们要求的是t的最小非负整数解。
t的公式可以通过(y0 + a / gcd(a, b)) % (a / gcd(a, b))得到。
(上述部分为了解释更清楚，和代码部分的字母有所不同。)

代码部分

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
#include<iostream>
#define int long long
using namespace std;
int exgcd(int a,int b,int &x,int &y)
{
	if (!b) {
		x=1,y=0;
		return a;
	}
	int d=exgcd(b,a%b,y,x);
	y-=a/b*x;
	return d;
}
signed main()
{
	int x0,y0,m,n,l;
	cin>>x0>>y0>>m>>n>>l;
	int x,y;
	int r=exgcd(l,n-m,x,y);
	if ((x0-y0)%r!=0) cout<<"Impossible\n";
		else {
			int t=(y*(x0-y0)/r%(l/r)+l/r)%(l/r);
			cout<<t<<endl;
		}
	return 0;
}

exgcd

题目描述

给出一个等式ax + by = c,计算可能的解(x0, y0)使得|x0 + y0|的值最小。
如果有多组解，输出其中的一种；如果无解，输出-1。

输入

t组数据，每组数据1行，包含a,b,c。其中-1e9 <= a,b,c <= 1e9, 1 <= T <= 1e5。

输出

同题目描述

样例输入

4
1 2 3
1 -1 -2
5 7 3
2 4 -3

样例输出

1 1
0 2
2 -1
-1

Note

在第二组数据中,(-1,1)也是一组可行解。

解释

首先判断a = 0,或者b = 0的一些情况，然后将a, b, c跑一次扩展欧几里得算法，得到一组解。我们要求的是绝对值之和最小的一组解。我的方法是：首先将x为最小非负整数的情况求出来，然后算出此时的y；然后将x为最大非正整数的情况求出来，算出此时的y；将y为最小非负整数的情况求出来，算出此时的x，将y为最大非正整数的情况求出来，算出此时的y。将这几种情况比较，就能得到最终绝对值之和最小的解。
不得不说，这题我的代码较为冗余丑陋。

代码部分

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
#include<iostream>
#define int long long
using namespace std;
int exgcd(int a,int b,int &x,int &y)
{
	if (!b) {
		x=1,y=0;
		return a;
	}
	int d=exgcd(b,a%b,y,x);
	y-=a/b*x;
	return d;
}
signed main()
{
	int t;
	cin>>t;
	while (t--) {
		int a,b,c;
		cin>>a>>b>>c;
		if (a==0&&b==0) {
			if (c==0) cout<<"0 0"<<endl;
				else cout<<-1<<endl;
			continue;
		}
		int x,y;
		int r=exgcd(a,b,x,y);
		if (c%r!=0) {
			cout<<-1<<endl;
			continue;
		}
		int x0=x*(c/r),y0=y*(c/r);
		pair<int,int> res;
		res.first=1e9+1,res.second=1e9+1;
		if (a==0||b==0) {
			cout<<x0<<' '<<y0<<endl;
			continue;
		}
		int xx,yy,k;
		xx=(x0+(b/r))%(b/r);
		k=(xx-x0)/(b/r);
		yy=y0-(a/r)*k;
		if (abs(xx)+abs(yy)<=abs(res.first)+abs(res.second)) {
			res.first=xx,res.second=yy;
		}
		xx-=(b/r);
		yy+=(a/r);
		if (abs(xx)+abs(yy)<=abs(res.first)+abs(res.second)) {
			res.first=xx,res.second=yy;
		}
		xx+=(b/r),xx+=(b/r);
		yy-=(a/r),yy-=(a/r);
		if (abs(xx)+abs(yy)<=abs(res.first)+abs(res.second)) {
			res.first=xx,res.second=yy;
		}
		yy=(y0+(a/r))%(a/r);
		k=(y0-yy)/(a/r);
		xx=x0+(b/r)*k;
		if (abs(xx)+abs(yy)<=abs(res.first)+abs(res.second)) {
			res.first=xx,res.second=yy;
		}
		xx+=(b/r);
		yy-=(a/r);
		if (abs(xx)+abs(yy)<=abs(res.first)+abs(res.second)) {
			res.first=xx,res.second=yy;
		}
		xx-=(b/r),xx-=(b/r);
		yy+=(a/r),yy+=(a/r);
		if (abs(xx)+abs(yy)<=abs(res.first)+abs(res.second)) {
			res.first=xx,res.second=yy;
		}
		cout<<res.first<<' '<<res.second<<endl;
	}
	return 0;
}

发表于 分类于

题目链接：VJ(private)

Simple Fibonacci

题目描述

求斐波那契数列第n项对于1004535809取模的值。

解释

正解是矩阵快速幂（之后补）。
我用了二次剩余的板子写，直接代入通项公式。

代码部分

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
#include<bits/stdc++.h>
using namespace std;
const long long p=1004535809;
long long f(long long a,long long b)
{
	long long ans=1;
	while (b) {
		if (b&1) ans=ans*a%p;
		a=a*a%p;
		b>>=1;
	}
	return ans;
}
long long TS(long long n)
{
    if (p==2) return (n&1)?1:-1;
    if (f(n,p>>1)+1==p) return -1;
    if (p&2) return f(n,p+1>>2);
    int s=__builtin_ctzll(p^1);
    long long q=p>>s,z=2;
    for (;f(z,p>>1)==1;++z);
    long long c=f(z,q),r=f(n,q+1>>1),t=f(n,q),tmp;
    for (int m=s,i;t!=1;) {
        for (i=0,tmp=t;tmp!=1;++i) tmp=tmp*tmp%p;
        for (;i<--m;) c=c*c%p;
        r=r*c%p;
        c=c*c%p;
        t=t*c%p;
    }
    return r;
}
const long long q=TS(5);
int main()
{
	long long n;
	cin>>n;
	cout<<f(q,p-2)*(f((1+q)*f(2,p-2)%p,n)-f((1-q)*f(2,p-2)%p,n)+p)%p;
	return 0;
}

发表于 分类于

题目链接：VJ(private)

Euler Sieve

题目描述

定义函数f为约数和函数和欧拉函数的卷积。求f前n项和。
1 <= n <= 5e6

解释

用欧拉筛（线性筛）筛素数的同时求出每项的欧拉函数和约数和函数。用双重循环将f的前n项和直接累加。

代码部分

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
#include<bits/stdc++.h>
using namespace std;
int prime[5050000];
bool flag[5050000];
int phi[5050000];
int f[5050000];
int g[5050000];
int cnt;
int main()
{
	int n;
	cin>>n;
	flag[1]=true;
	phi[1]=f[1]=g[1]=1;
	for (int i=1;i<=n;i++) {
		if (!flag[i]) {
			prime[++cnt]=i;
			phi[i]=i-1;
			f[i]=i+1;
			g[i]=i+1;
		}
		for (int j=1;j<=cnt&&i*prime[j]<=n;j++) {
			flag[i*prime[j]]=true;
			if (i%prime[j]==0) {
				phi[i*prime[j]]=phi[i]*prime[j];
				g[i*prime[j]]=g[i]*prime[j]+1;
				f[i*prime[j]]=f[i]/g[i]*g[i*prime[j]];
				break;
			}
			phi[i*prime[j]]=phi[i]*(prime[j]-1);
			f[i*prime[j]]=f[i]*f[prime[j]];
			g[i*prime[j]]=1+prime[j];
		}
	}
	long long ans=0;
	for (int i=1;i<=n;i++) 
		for (int j=1;j<=n/i;j++)
			ans+=phi[i]*f[j];
	cout<<ans<<endl;
	return 0;
}

补充

积性函数可以用欧拉筛来求出每一项值。常见的积性函数有欧拉函数、莫比乌斯函数、约数个数函数、约数和函数。
以下是oi-wiki中求四种积性函数的代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 欧拉函数
void pre() {
  memset(is_prime, 1, sizeof(is_prime));
  int cnt = 0;
  is_prime[1] = 0;
  phi[1] = 1;
  for (int i = 2; i <= 5000000; i++) {
    if (is_prime[i]) {
      prime[++cnt] = i;
      phi[i] = i - 1;
    }
    for (int j = 1; j <= cnt && i * prime[j] <= 5000000; j++) {
      is_prime[i * prime[j]] = 0;
      if (i % prime[j])
        phi[i * prime[j]] = phi[i] * phi[prime[j]];
      else {
        phi[i * prime[j]] = phi[i] * prime[j];
        break;
      }
    }
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 莫比乌斯函数
void pre() {
  mu[1] = 1;
  for (int i = 2; i <= 1e7; ++i) {
    if (!v[i]) mu[i] = -1, p[++tot] = i;
    for (int j = 1; j <= tot && i <= 1e7 / p[j]; ++j) {
      v[i * p[j]] = 1;
      if (i % p[j] == 0) {
        mu[i * p[j]] = 0;
        break;
      } else {
        mu[i * p[j]] = -mu[i];
      }
    }
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 求约数个数函数
void pre() {
  d[1] = 1;
  for (int i = 2; i <= n; ++i) {
    if (!v[i]) v[i] = 1, p[++tot] = i, d[i] = 2, num[i] = 1;
    for (int j = 1; j <= tot && i <= n / p[j]; ++j) {
      v[p[j] * i] = 1;
      if (i % p[j] == 0) {
        num[i * p[j]] = num[i] + 1;
        d[i * p[j]] = d[i] / num[i * p[j]] * (num[i * p[j]] + 1);
        break;
      } else {
        num[i * p[j]] = 1;
        d[i * p[j]] = d[i] * 2;
      }
    }
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 求约数和函数
void pre() {
  g[1] = f[1] = 1;
  for (int i = 2; i <= n; ++i) {
    if (!v[i]) v[i] = 1, p[++tot] = i, g[i] = i + 1, f[i] = i + 1;
    for (int j = 1; j <= tot && i <= n / p[j]; ++j) {
      v[p[j] * i] = 1;
      if (i % p[j] == 0) {
        g[i * p[j]] = g[i] * p[j] + 1;
        f[i * p[j]] = f[i] / g[i] * g[i * p[j]];
        break;
      } else {
        f[i * p[j]] = f[i] * f[p[j]];
        g[i * p[j]] = 1 + p[j];
      }
    }
  }
}

发表于 分类于

题目链接：VJ(private) [POJ]

Prime Distance

题目描述

The branch of mathematics called number theory is about properties of numbers. One of the areas that has captured the interest of number theoreticians for thousands of years is the question of primality. A prime number is a number that is has no proper factors (it is only evenly divisible by 1 and itself). The first prime numbers are 2,3,5,7 but they quickly become less frequent. One of the interesting questions is how dense they are in various ranges. Adjacent primes are two numbers that are both primes, but there are no other prime numbers between the adjacent primes. For example, 2,3 are the only adjacent primes that are also adjacent numbers.
Your program is given 2 numbers: L and U (1<=L< U<=2,147,483,647), and you are to find the two adjacent primes C1 and C2 (L<=C1< C2<=U) that are closest (i.e. C2-C1 is the minimum). If there are other pairs that are the same distance apart, use the first pair. You are also to find the two adjacent primes D1 and D2 (L<=D1< D2<=U) where D1 and D2 are as distant from each other as possible (again choosing the first pair if there is a tie).

输入：

Each line of input will contain two positive integers, L and U, with L < U. The difference between L and U will not exceed 1,000,000.

输出：

For each L and U, the output will either be the statement that there are no adjacent primes (because there are less than two primes between the two given numbers) or a line giving the two pairs of adjacent primes.

样例输入1

2 17
14 17

样例输出1

2,3 are closest, 7,11 are most distant.
There are no adjacent primes.

解释

题目的意思是寻找区间内距离最小的相邻素数对，和距离最大的相邻素数对。

由于区间大小|U - L|限制在1e6以下，考虑使用区间筛。先筛出1~50000之间的素数，然后用这些素数筛掉区间内的合数，遍历一次区间，将素数取出并储存到vector中，计算相邻素数的距离最大最小值。

代码部分

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
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<cstring>
#define int long long
using namespace std;
int prime[1020000];
bool f[1020000];
bool sh[1002000];
int cnt;
signed main()
{
	f[1]=true;
	for (int i=2;i<=50000;i++) {
		if (!f[i]) prime[++cnt]=i;
		for (int j=1;j<=cnt&&i*prime[j]<=50000;j++) {
			f[i*prime[j]]=true;
			if (i%prime[j]==0) break;
		}
	}
	int l,r;
	while (~scanf("%lld%lld",&l,&r)) {
		memset(sh,0,sizeof(sh));
		if (l==1) l++;
		for (int i=1;i<=cnt;i++) 
			for (int j=max((l+prime[i]-1)/prime[i]*prime[i],2*prime[i]);j<=r;j+=prime[i]) 
				sh[j-l]=true;
		vector<int> vec;
		for (int i=l;i<=r;i++)
			if (!sh[i-l]) vec.push_back(i);
		if (vec.size()<=1) printf("There are no adjacent primes.\n");
		else {
			int prev=vec[0];
			int mi=1e9,ma=-1;
			pair<int,int> p1,p2;
			for (int i=1;i<vec.size();i++) {
				int d=vec[i]-prev;
				if (d<mi) {
					mi=d;
					p1.first=prev;
					p1.second=vec[i];
				}
				if (d>ma) {
					ma=d;
					p2.first=prev;
					p2.second=vec[i];
				}
				prev=vec[i];
			}
			printf("%lld,%lld are closest, %lld,%lld are most distant.\n",p1.first,p1.second,p2.first,p2.second);
		}
	}
	return 0;
}

发表于 更新于 分类于

题目链接：VJ

题目描述

There were a lot of balls in the factory of Ball Illusion Technology(BIT). Link, a boy, went there to get some balls, but suddenly, he found that there were too many ways to get balls.

There are 2n buckets in the factory. Link may get kx balls from the 2x−1th bucket, where k is a non-negtive integer. He may also get at most x balls from the 2xth bucket.

Link wanted to get m balls, and he wondered how many ways there were to take out exactly m balls. While Link is calculating the answer, he wants you to calculate it as well, and you should output the answer modulo 10^9+7

输入：

The input consists of multiple test cases.

The first line contains an integer T (1 <= T <= 1e5) – the number of test cases.

Each test case contains two integers n and m (1 <= n, m <= 1e6)

输出：

For each test case, print the answer modulo 1e9+7 in a single line.

样例输入1

4
1 1
2 2
3 3
1000000 1000000

样例输出1

2
6
20
192151600

解释

题目的意思是一共有2n个篮子。第奇数(2x-1)个篮子可以拿kx个球，k为任意非负整数；第偶数(2x)个篮子可以拿[0,x]个球。问在这2n个篮子中拿取m个球有多少种情况，答案模1e9+7。

先考虑第一个篮子，1是奇数，也就是说我们在第一个篮子可以拿任意非负整数个球；那么之后的篮子呢？我们可以考虑将篮子合并，考虑第2个和第3个篮子。第2个篮子可以拿0,1个球，第3个篮子可以拿2k个球。那么把第2个篮子和第3个篮子加起来，也就是说，可以取2k个球或者2k+1个球，而k是非负整数，也就是说，第2个篮子和第3个篮子合并后也可以取任意个球。同样的，考虑第4个和第5个篮子，可以取3k,3k+1,3k+2个球，也是全体非负整数。由此推广，我们可以发现，第2n-2个和第2n-1个篮子，可以取kn+b,b∈[0,n-1],取遍全体非负整数。（不知为什么，写到这里，脑子突然想到了完全剩余系这个概念/doge）然后第2n个篮子单独拎出来。

第一步就这样完成了，经过合并，我们把2n个篮子分成了两部分。第一部分是n个可以取任意球的篮子，第二部分是只能取[0,n]个球的第n+1个篮子。我们的目的是找出在这n+1个篮子中取出m个球的方法数。

我们用组合数学的思维来思考问题。将第n+1个篮子中所取的球数从0到n开始枚举（先考虑m>=n)。假设第n+1个篮子中，我们取i个球，则我们剩下要取的球数就是m-i个球。我们的最终模型就变成了：对于每一个给定的i，在n个篮子，可以取[0,+∞)个球，要取m-i个球的方法数。

我们可以想到高中学过的隔板法。即 a1+a2+a3+a4+……+an=m-i 这一不定方程的正整数解的个数。略有区别的是，我们的球可以不取。为了适配隔板法，我们把初始球数均设为1，式子变成了 (a1-1)+(a2-1)+(a3-1)+……+(an-1)=m+n-i。我们用隔板法可以很快把式子写出来了:$C_{m+n-i-1}^{n-1}$。

第二步完成了。得到这个公式后，因为我们要将i从0到n代入并累加，并没有办法很快得到结果。我们要把公式进行转化。

这里有一个组合数公式。$C_{n}^{m}$=$C_{n-1}^{m}$+$C_{n-1}^{m-1}$。将我们得到的式子 $\sum_{i=0}^{n}$ $C_{m+n-i-1}^{n-1}$ 展开，即 $C_{m+n-1}^{n-1}$+$C_{m+n}^{n-1}$+……+$C_{m-1}^{n-1}$，然后先加上一个 $C_{m-1}^{n}$ ，和原来的式子一一合并，得到 $C_{m+n}^{n}$，然后减去之前加上的 $C_{m-1}^{n}$，就是最后我们用代码直接实现的公式。即 $C_{m+n}^{n}$-$C_{m-1}^{n}$。

第三步完成了。

代码部分还有需要注意的。当组合数出现不符合定义时，我们返回0，也刚好可以处理之前篮子数比所需取出的球数多的情况。由于数据较大，而且组合数中用到了除法，使用快速幂和逆元求解。关于快速幂和逆元，这里不再详细解释。

代码部分

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
#include<iostream>
using namespace std;
const int mod=1e9+7;
long long jc[2020000];
long long f(long long a,long long b)
{
	long long ans=1;
	while (b) {
		if (b&1) {
			ans=ans*a%mod;
		}
		a=a*a%mod;
		b>>=1;
	}
	return ans%mod;
}
long long c(long long a,long long b)
{
	if (a>b) return 0;
	return jc[b]*f(jc[a],mod-2)%mod*f(jc[b-a],mod-2)%mod;
}
int main()
{
	jc[0]=1;
	for (int i=1;i<=2000020;i++)
		jc[i]=jc[i-1]*i%mod;
	int t;
	scanf("%d",&t);
	while (t--) {	
		int n,m;
		scanf("%d%d",&n,&m);
		long long ans=c(n,m+n)-c(n,m-1)+mod;
		printf("%lld\n",ans%mod);
	}
	return 0;
}

发表于 分类于

题干

甲和乙玩数字游戏，两人分别将 1 ~ n 之间的数字以一定次序排成 a1, ……, an 和 b1, ……, bn, 将数字逐个比较。 若ai > bi, 则甲得一分；若ai < bi, 则乙得一分；若ai = bi, 则不计分。
设Pn为数字范围为 1 ~ n 时甲乙得分相等的概率。
(1) 当 n = 5 时， 求Pn
(2) 求Pn通项公式
(3) 求 $\lim\limits_{n\rightarrow\infty}P(n)$

花絮

这道题源自于苦逼的高三生活。埋在题海中，时常会有奇怪的灵感与想法，我就将它记了下来。虽然至今还是不会做来着。

发表于 更新于 分类于

题目链接：暂无

T1 分糖果

【题目背景】

红太阳幼儿园的小朋友们开始分糖果啦！

【题目描述】

红太阳幼儿园有 n 个小朋友，你是其中之一。保证 n ≥ 2。
有一天你在幼儿园的后花园里发现无穷多颗糖果，你打算拿一些糖果回去分给幼儿园的小朋友们。
由于你只是个平平无奇的幼儿园小朋友，所以你的体力有限，至多只能拿 R 块糖回去。
但是拿的太少不够分的，所以你至少要拿 L 块糖回去。保证 n ≤ L ≤ R。
也就是说，如果你拿了 k 块糖，那么你需要保证 L ≤ k ≤ R。
如果你拿了 k 块糖，你将把这 k 块糖放到篮子里，并要求大家按照如下方案分糖果：只要篮子里有不少于 n 块糖果，幼儿园的所有 n 个小朋友（包括你自己）都从篮子中拿走恰好一块糖，直到篮子里的糖数量少于 n 块。此时篮子里剩余的糖果均归你所有——这些糖果是作为你搬糖果的奖励。
作为幼儿园高质量小朋友，你希望让作为你搬糖果的奖励的糖果数量（而不是你最后获得的总糖果数量！）尽可能多；因此你需要写一个程序，依次输入 n, L, R, 并输出出你最多能获得多少作为你搬糖果的奖励的糖果数量。

【输入格式】

输入一行，包含三个正整数 n, L, R, 分别表示小朋友的个数、糖果数量的下界和上界。

【输出格式】

输出一行一个整数，表示你最多能获得的作为你搬糖果的奖励的糖果数量。

【输入输出样例】

输入 #1
7 16 23
输出 #1
6
输入 #2
10 14 18
输出 #2
8

说明/提示

【样例解释 #1】
拿 k = 20 块糖放入篮子里。
篮子里现在糖果数 20 ≥ n = 7，因此所有小朋友获得一块糖；
篮子里现在糖果数变成 13 ≥ n = 7，因此所有小朋友获得一块糖；
篮子里现在糖果数变成 6 < n = 7，因此这 6 块糖是作为你搬糖果的奖励。
容易发现，你获得的作为你搬糖果的奖励的糖果数量不可能超过 6 块（不然，篮子里的糖果数量最后仍然不少于 n ，需要继续每个小朋友拿一块），因此答案是 6。

【样例解释 #2】
容易发现，当你拿的糖数量 k 满足 14 = L ≤ k ≤ R = 18 时，所有小朋友获得一块糖后，剩下的 k−10 块糖总是作为你搬糖果的奖励的糖果数量，因此拿 k=18 块是最优解，答案是 8。

【数据范围】

【解题思路】

看看n的整数倍是否在[L,R]的区间内，如果是，则取余数最大的时候，即余数为n-1时；
如果不是，则取R件糖果，使得取余后剩下的糖果最多。

【代码部分】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long n,l,r;
    cin>>n>>l>>r;
    long long x,y;
    x=l/n;
    y=r/n;
    if (y>x) {
        long long ans=y*n-1;
        cout<<ans%n<<endl;
    }
    if (x==y) {
        cout<<r%n<<endl;
    }
    return 0;
}

T2 插入排序

【题目描述】

插入排序是一种非常常见且简单的排序算法。小 Z 是一名大一的新生，今天 H 老师刚刚在上课的时候讲了插入排序算法。
假设比较两个元素的时间为 O(1)，则插入排序可以以 O(n^2) 的时间复杂度完成长度为 n 的数组的排序。不妨假设这 n 个数字分别存储在a1,a2,…,an之中，则如下伪代码给出了插入排序算法的一种最简单的实现方式：
这下面是 C/C++ 的示范代码

1
2
3
4
5
6
7
for (int i = 1; i <= n; i++)
	for (int j = i; j >= 2; j--)
		if (a[j] < a[j-1]) {
			int t = a[j-1];
			a[j-1] = a[j];
			a[j] = t;
		}

这下面是 Pascal 的示范代码

1
2
3
4
5
6
7
8
for i:=1 to n do
	for j:=i downto 2 do
		if a[j]<a[j-1] then
			begin
				t:=a[i];
				a[i]:=a[j];
				a[j]:=t;
			end;

为了帮助小 Z 更好的理解插入排序，小 Z 的老师 H 老师留下了这么一道家庭作业：
H 老师给了一个长度为 n 的数组 a ，数组下标从 1 开始，并且数组中的所有元素均为非负整数。小 Z 需要支持在数组 a 上的 Q 次操作，操作共两种，参数分别如下：
1 x v：这是第一种操作，会将 a 的第 x 个元素，也就是 ax 的值，修改为 v 。保证 1 ≤ x ≤ n ，1 ≤ v ≤ 109 。注意这种操作会改变数组的元素，修改得到的数组会被保留，也会影响后续的操作。
2 x：这是第二种操作，假设 H 老师按照上面的伪代码对 a 数组进行排序，你需要告诉 H 老师原来 a 的第 x 个元素，也就是 ax，在排序后的新数组所处的位置。保证 1 ≤ x ≤ n 。注意这种操作不会改变数组的元素，排序后的数组不会被保留，也不会影响后续的操作。
H 老师不喜欢过多的修改，所以他保证类型 1 的操作次数不超过 5000 。
小 Z 没有学过计算机竞赛，因此小 Z 并不会做这道题。他找到了你来帮助他解决这个问题。

【输入格式】

第一行，包含两个正整数 n , Q ，表示数组长度和操作次数。
第二行，包含 n 个空格分隔的非负整数，其中第 i 个非负整数表示 ai。
接下来 Q 行，每行 2 ∼ 3 个正整数，表示一次操作，操作格式见【题目描述】。

【输出格式】

对于每一次类型为 2 的询问，输出一行一个正整数表示答案。

【输入输出样例】

输入 #1
3 4
3 2 1
2 3
1 3 2
2 2
2 3
输出 #1
1
1
2

【说明/提示&数据范围】

T3 网络连接

【题目描述】

TCP/IP 协议是网络通信领域的一项重要协议。今天你的任务，就是尝试利用这个协议，还原一个简化后的网络连接场景。
在本问题中，计算机分为两大类：服务机（Server）和客户机（Client）。服务机负责建立连接，客户机负责加入连接。
需要进行网络连接的计算机共有 n 台，编号为 1 ∼ n ，这些机器将按编号递增的顺序，依次发起一条建立连接或加入连接的操作。
每台机器在尝试建立或加入连接时需要提供一个地址串。服务机提供的地址串表示它尝试建立连接的地址，客户机提供的地址串表示它尝试加入连接的地址。
一个符合规范的地址串应当具有以下特征：
必须形如 a.b.c.d:e 的格式，其中 a , b , c , d , e 均为非负整数；
0 ≤ a , b , c , d ≤ 255 ，0 ≤ e ≤ 65535 ；
a , b , c , d , e 均不能含有多余的前导 0 。
相应地，不符合规范的地址串可能具有以下特征：
不是形如 a.b.c.d:e 格式的字符串，例如含有多于 3 个字符 . 或多于 1 个字符 : 等情况；
整数 a , b , c , d , e 中某一个或多个超出上述范围；
整数 a , b , c , d , e 中某一个或多个含有多余的前导 0 。
例如，地址串 192.168.0.255:80 是符合规范的，但 192.168.0.999:80、192.168.00.1:10、192.168.0.1:088、192:168:0:1.233 均是不符合规范的。
如果服务机或客户机在发起操作时提供的地址串不符合规范，这条操作将被直接忽略。
在本问题中，我们假定凡是符合上述规范的地址串均可参与正常的连接，你无需考虑每个地址串的实际意义。
由于网络阻塞等原因，不允许两台服务机使用相同的地址串，如果此类现象发生，后一台尝试建立连接的服务机将会无法成功建立连接；除此之外，凡是提供符合规范的地址串的服务机均可成功建立连接。
如果某台提供符合规范的地址的客户机在尝试加入连接时，与先前某台已经成功建立连接的服务机提供的地址串相同，这台客户机就可以成功加入连接，并称其连接到这台服务机；如果找不到这样的服务机，则认为这台客户机无法成功加入连接。
请注意，尽管不允许两台不同的服务机使用相同的地址串，但多台客户机使用同样的地址串，以及同一台服务机同时被多台客户机连接的情况是被允许的。
你的任务很简单：在给出每台计算机的类型以及地址串之后，判断这台计算机的连接情况。

【输入格式】

第一行，一个正整数 n 。
接下来 n 行，每行两个字符串 op, ad，按照编号从小到大给出每台计算机的类型及地址串。
其中 op 保证为字符串 Server 或 Client 之一，ad 为一个长度不超过 25 的，仅由数字、字符 . 和字符 : 组成的非空字符串。
每行的两个字符串之间用恰好一个空格分隔开，每行的末尾没有多余的空格。

【输出格式】

输出共 n 行，每行一个正整数或字符串表示第 i 台计算机的连接状态。其中：
如果第 i 台计算机为服务机，则：
如果其提供符合规范的地址串且成功建立连接，输出字符串 OK。
如果其提供符合规范的地址串，但由于先前有相同地址串的服务机而无法成功建立连接，输出字符串 FAIL。
如果其提供的地址串不是符合规范的地址串，输出字符串 ERR。
如果第 i 台计算机为客户机，则：
如果其提供符合规范的地址串且成功加入连接，输出一个正整数表示这台客户机连接到的服务机的编号。
如果其提供符合规范的地址串，但无法成功加入连接时，输出字符串 FAIL。
如果其提供的地址串不是符合规范的地址串，输出字符串 ERR。

【输入输出样例】

输入 #1
5
Server 192.168.1.1:8080
Server 192.168.1.1:8080
Client 192.168.1.1:8080
Client 192.168.1.1:80
Client 192.168.1.1:99999
输出 #1
OK
FAIL
1
FAIL
ERR

输入 #2
10
Server 192.168.1.1:80
Client 192.168.1.1:80
Client 192.168.1.1:8080
Server 192.168.1.1:80
Server 192.168.1.1:8080
Server 192.168.1.999:0
Client 192.168.1.1.8080
Client 192.168.1.1:8080
Client 192.168.1.1:80
Client 192.168.1.999:0
输出 #2
OK
1
FAIL
FAIL
OK
ERR
ERR
5
1
ERR

【说明/提示】

【样例解释 #1】
计算机 1 为服务机，提供符合规范的地址串 192.168.1.1:8080，成功建立连接；
计算机 2 为服务机，提供与计算机 1 11 相同的地址串，未能成功建立连接；
计算机 3 为客户机，提供符合规范的地址串 192.168.1.1:8080，成功加入连接，并连接到服务机 1 ；
计算机 4 为客户机，提供符合规范的地址串 192.168.1.1:80，找不到服务机与其连接；
计算机 5 为客户机，提供的地址串 192.168.1.1:99999 不符合规范。

【数据范围】

【解题思路】

Op保证为Server或者Client之一，那就免去了判错的步骤，我不太会用switch，就直接if分类讨论Op的两种情况。不管是服务机还是客户机，都需要判断两个基本的条件：地址串是否符合规范，先前是否有相同地址串。
地址串是否符合规范的判断，写在主函数中属实有点让人眼花缭乱，所以我把它放在子函数conn（随便取的）中。由于地址串中a，b，c，d，e元素的位数不确定，所以可以视作.和：把五个元素分割开了。把它们强制取出来，同时判断是否有前置0，最后判断每个数字具体大小是否在规定区间内。（程序仍有部分问题，比如输入…:也会显示OK）
先前是否有相同地址串的判断，可以想到STL库中的集合，即set容器。Insert可以在容器内添加元素，count可以用来判断该元素是否在容器内。有了这两个方法，程序就变得容易（无脑）些了。
服务机和客户机的操作略有不同，但大同小异。直接按照题目输出中的逻辑，书写代码即可。有了之前的铺垫，就会好写很多。

【代码部分】

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
#include<bits/stdc++.h>
using namespace std;
bool conn(string s) 
{
    int n=0,a=0,b=0,c=0,d=0,e=0;
    if (s[n]=='0'&&s[n+1]!='.') return false;
    while (s[n]!='.'&&n<s.length()) {
        a=a*10+int(s[n])-48;
        n++; 
    }
    n++;
    if (s[n]=='0'&&s[n+1]!='.') return false;
    while (s[n]!='.'&&n<s.length()) {
        b=b*10+int(s[n])-48;
        n++; 
    }
    n++;
    if (s[n]=='0'&&s[n+1]!='.') return false;
    while (s[n]!='.'&&n<s.length()) {
        c=c*10+int(s[n])-48;
        n++; 
    }
    n++;
    if (s[n]=='0'&&s[n+1]!=':') return false;
    while (s[n]!=':'&&n<s.length()) {
        d=d*10+int(s[n])-48;
        n++;
    }
    n++;
    if (s[n]=='0') return false;
    for (int i=n;i<s.length();i++) {
        e=e*10+int(s[i])-48;
    }
    if (a>=0&&a<=255&&b>=0&&b<=255&&c>=0&&c<=255&&d>=0&&d<=255&&e>=0&&e<=65535)
        return true;
    return false;
}
int main()
{
    int n;
    string op,ad;
    set<string> comp;
    string ss[1020];
    cin>>n;
    for (int i=1;i<=n;i++) {
        cin>>op>>ad;
        bool flag=conn(ad);
        if (op=="Server") {
            if (flag&&comp.count(ad)==0) {
                comp.insert(ad);
                ss[i]=ad;
                cout<<"OK\n";
            }
            else if (flag&&comp.count(ad)!=0) 
                cout<<"FAIL\n";
            else if (!flag) cout<<"ERR\n";
        }
        else if (op=="Client") {
            if (flag&&comp.count(ad)!=0) {
                for (int j=1;j<=n;j++)
                    if (ad==ss[j]) cout<<j<<endl;
            }
            else if (flag&&comp.count(ad)==0) 
                cout<<"FAIL\n";
            else if (!flag) cout<<"ERR\n";
        }
    }
    return 0;   
}

T4 小熊的果篮

【题目描述】

小熊的水果店里摆放着一排 n 个水果。每个水果只可能是苹果或桔子，从左到右依次用正整数 1、2、3、……、n 编号。连续排在一起的同一种水果称为一个“块”。小熊要把这一排水果挑到若干个果篮里，具体方法是：每次都把每一个“块”中最左边的水果同时挑出，组成一个果篮。重复这一操作，直至水果用完。注意，每次挑完一个果篮后，“块”可能会发生变化。比如两个苹果“块”之间的唯一桔子被挑走后，两个苹果“块”就变成了一个“块”。请帮小熊计算每个果篮里包含的水果。

【输入格式】

输入的第一行包含一个正整数 n，表示水果的数量。
输入的第二行包含 n 个空格分隔的整数，其中第 i 个数表示编号为 i 的水果的种类，1 代表苹果，0 代表桔子。

【输出格式】

输出若干行。
第 i 行表示第 i 次挑出的水果组成的果篮。
从小到大排序输出该果篮中所有水果的编号，每两个编号之间用一个空格分隔。

【输入输出样例】

输入 #1
12
1 1 0 0 1 1 1 0 1 1 0 0
输出 #1
1 3 5 8 9 11
2 4 6 12
7
10
输入 #2
20
1 1 1 1 0 0 0 1 1 1 0 0 1 0 1 1 0 0 0 0
输出 #2
1 5 8 11 13 14 15 17
2 6 9 12 16 18
3 7 10 19
4 20

【说明/提示】

【样例解释 #1】
这是第一组数据的样例说明。
所有水果一开始的情况是 [1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0] ，一共有 6 个块。
在第一次挑水果组成果篮的过程中，编号为 1 , 3 , 5 , 8 , 9 , 11 的水果被挑了出来。
之后剩下的水果是 [1, 0, 1, 1, 1, 0] ，一共 4 个块。
在第二次挑水果组成果篮的过程中，编号为 2, 4, 6, 12 的水果被挑了出来。
之后剩下的水果是 [1, 1] ，只有 1 个块。
在第三次挑水果组成果篮的过程中，编号为 7 的水果被挑了出来。
最后剩下的水果是 [1] ，只有 1 个块。
在第四次挑水果组成果篮的过程中，编号为 10 的水果被挑了出来。

【数据范围】

对于 10% 的数据，n ≤ 5 。
对于 30% 的数据，n ≤ 1000 。
对于 70% 的数据，n ≤ 50000 。
对于 100% 的数据，1 ≤ n ≤ 2 × 105

【解题思路】

首先，因为水果会被挑出，相当于会有数据的删除，所以我们会想到用列表容器来解决这道题目。STL库中有list容器，使用它应该会方便许多。
我定义了a，b两个List。a用来储存水果的种类，b用来储存水果的编号。由于不知道要进行多少次挑水果的操作，所以我用while(1)来开始循环。被挑走的水果具有的特征是与之前相邻一个的水果类型不同。而第一个水果肯定是要被挑走的，所以我们默认第0个水果的种类为-1。将a，b两个链表的迭代器同时遍历，如果元素满足上述条件，就输出，并记录它的位置，等到迭代器到下一个位置时，再将所记录的位置的元素删除。（这是一个坑，如果不等到迭代器到下一个位置，直接删除，会出问题）而我们退出循环的条件就是list容器的元素个数为0。

【代码部分】

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;
int main()
{
	int n,x,y;
	scanf("%d",&n);
	list<int> a;
	list<int> b;
	list<int>::iterator ita,itb,itaa,itbb;
	for (int i=1;i<=n;i++) {
		scanf("%d",&x);
		a.push_back(x);
		b.push_back(i);
	}	
	while (1) {
		int fruit=-1;
		bool flag=false;
		itb=b.begin();
		for (ita=a.begin();ita!=a.end();ita++) {
			if (flag) {
				a.erase(itaa);
				b.erase(itbb);
				flag=false;
			}
			if ((*ita)!=fruit) {
				fruit=*ita;
				printf("%d ",*itb);
				itaa=ita; itbb=itb;
				flag=true;
			}
			itb++;
		}
		if (flag) {
			a.erase(itaa);
			b.erase(itbb);
			flag=false;
		}
		printf("\n");
		if (a.size()<=0) break;
	} 
	return 0;
}

发表于 更新于 分类于

题目链接：暂无

题目描述

求有多少种长度为 n 的序列 A，满足以下条件：

  • 1∼n 这 n 个数在序列中各出现了一次；
  • 若第 i 个数 Ai 的值为 i，则称 i 是稳定的。序列恰好有 m 个数是稳定的。
    满足条件的序列可能很多，序列数对 10 ^ 9 + 7 取模。

输入：

第一行一个数 T，表示有 T 组数据。
接下来 T 行，每行两个整数 n、m。

输出：

输出 T 行，每行一个数，表示求出的序列数。

样例输入1

5
1 0
1 1
5 2
100 50
10000 5000

样例输出1

0
1
20
578028887
60695423

解释

遇到这道题两次了
我觉得这道题的知识点非常有趣
首先，错排公式我在高中数学中就接触过，就相当于n个人各有一个座位，每个人都坐在别人的位置上的种数。
前几项是0 1 2 9 44 265
我对这个数列非常喜欢
2=(0+1)*2
9=(1+2)*3
44=(2+9)*4
265=(9+44)*5
a[n]=(a[n-1]+a[n-2])*(n-1)
至于通项公式也可以推一推或者上网搜一搜
可以看出
这道题的意思就是其中的m个数在原来的位置，剩下的(n-m)个数进行了错排
也就是
C(m,n)*a[n-m]
但这个数据很大，题目说需要取模
那我们很容易就把阶乘和错排的数组边乘边取模给做完了
C(m,n)中有一步除以(n-m)!的过程该怎么办呢？
这时我们想到可以求逆元
费马小定理是指
如果p是一个质数，而整数a不是p的倍数，则有a^(p-1) ≡ 1 (mod p)
由费马小定理可知
a * a ^ (p-2) ≡ 1 (mod p)
a ^ (p-2) ≡ 1/a (mod p)
因此可知逆元就是a^(p-2)%p
因此我们做了一个存放逆元的数组
是不是直接输出就好了呢？
我们试了一下发现TLE
因此快快用上快速幂模板来加快我们求逆元的速度
快速幂这个算法体现了分治的思想
把每次的乘方拆成两半来解决
速度一下子就减了不少
我们试着交了一下，AC！

代码部分

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
#include<bits/stdc++.h>
using namespace std;
const long long k=1e9+7;
long long cp[1000020],jc[1000020],ny[1000020];
int f(long long a,long long b)   //快速幂模板
{
	long long ans = 1;
	while (b>0) {
		if (b%2==1) ans=ans*a%k;
		b/=2;
		a=a*a%k;
	}
	return ans;
}
int main()
{
	cp[0]=1,cp[2]=1;
	for (int i=3;i<=1000000;i++)
		cp[i]=(i-1)*(cp[i-1]+cp[i-2])%k;//cp即由错排公式从第0~n个元素组成的数组
	jc[0]=1,jc[1]=1;
	for (int i=2;i<=1000000;i++)
		jc[i]=jc[i-1]*i%k;//jc即阶乘
	ny[0] =f(jc[0],k - 2);
	for (int i=1;i<=1000000;i++)
		ny[i]=f(jc[i],k-2)%k;//ny即逆元
	int t;
	cin>>t;
	for (int i=1;i<=t;i++) {
		long long n,m;
		cin>>n>>m;
		cout<<(jc[n]*ny[m]%k*ny[n-m]%k*cp[n-m])%k<<endl;
	}
	return 0;
}

收获

  • 学到了快速幂模板
  • 学到了用费马小定理推得的逆元，成功解决了除法取模的问题。

发表于 更新于 分类于

题目链接：洛谷 Codeforces

题目描述

最近，Polycarp开始开发一种仅适用于正确括号序列（缩写为CBS）的文本编辑器。请注意，如果可以通过添加“+”-s和“1”-s来获得正确的数学表达式，则括号序列是正确的。例如，序列“（（））（）”“（）”和“（（）（（）））”是正确的，而“）（”“（（）”和“（（）））（”是不正确的。CBS中的每个括号都有一对。例如，在“（（）（（）））”中：
第1个括号与第8个括号配对，
第2个括号与第3个括号配对，
第3个括号与第2个括号配对，
第4个括号与第7个括号配对，
第5个括号与第6个括号配对，
第6个括号与第5个括号配对，
第7个括号与第4个括号配对，
第8个括号与第1个括号配对。
Polycarp的编辑器目前在使用CBS期间仅支持三种操作。编辑器中的光标占据其中一个括号的整个位置（而不是括号之间的位置！）。支持三种操作：
«L»-将光标向左移动一个位置，
«R»-将光标向右移动一个位置，
«D»-删除光标所在的括号，删除与其配对的括号以及它们之间的所有括号（即，删除光标所在的括号和与其配对的括号之间的子字符串）。
操作“D”后，光标移动到最右边的括号中（当然，在未删除的括号中）。如果没有这样的括号（即，CBS的后缀已被删除），则光标将移动到最靠近左侧的括号（当然，在未删除的括号中）。
下面的图片说明了操作“D”的几种用法。

Polycarp的编辑器不支持所有不正确的操作（将光标移到CBS的末尾，删除整个CBS等）。
Polycarp对他的开发感到非常自豪，你能实现他的编辑器的功能吗？

输入：

第一行包含三个正整数n、m和p（2≤N≤500000, 1≤M≤500000, 1≤P≤n）——正确括号顺序中括号的数量、操作的数量和光标的初始位置。序列中的位置从左到右编号，从1开始。保证n是偶数。
它后面是由n个字符组成的字符串“（“和”）”，构成正确的括号序列。
然后跟随一个由m个字符组成的字符串“L”“R”和“D”——一系列操作。从第一个到最后一个，一个接一个地进行操作。可以保证给定的操作不会将光标移到括号序列之外，并且在所有操作之后，括号序列将是非空的。

输出：

打印正确的括号顺序，这是对初始顺序应用所有操作后获得的结果。

样例输入1

8 4 5
(())()()
RDLD

样例输出1

()

样例输入2

12 5 3
((()())(()))
RRDLD

样例输出2

(()(()))

样例输入3

8 8 8
(())()()
LLLLLLDD

样例输出3

()()

提示：

在第一个样例中，光标最初位于位置5。考虑编辑的过程：命令“R”-光标移动到右侧的位置6；命令“D”-从位置5到位置6删除括号。在CBS采取形式（（））（）之后，光标位于位置5；命令“L”-光标移动到左侧的位置4；命令“D”-从位置1到位置4删除括号。在CBS采用（）形式之后，光标位于位置1。
因此，答案等于（）。

代码&注释部分

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
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,m,p;
	char c;
	list<char> a;
	cin>>n>>m>>p;
	a.push_back('!');		//在链表头设置围栏 
	for (int i=1;i<=n;i++) {
		cin>>c;
		a.push_back(c);		 
	}
	list<char>::iterator it;
	list<char>::iterator posBeg,posEnd;		//所要删除的起始位和终止位 
	list<char>::iterator temp;	
	it=a.begin();	
	it++;					//起始值为原起始值后面一位 
	for (int i=2;i<=p;i++) it++;	//后移至p位 
	for (int i=1;i<=m;i++) {
		cin>>c;
		if (c=='R') it++;	//R指令右移一位 
		if (c=='L') it--;	//L指令左移一位 
		if (c=='D') {
			if (*it=='(') {	//D指令判断是否左括号 
				posBeg=it;	//所要删除的起始位在当前位置 
				posEnd=it;
				posEnd++;	
				int cnt=1;	//当前位置为(所以要向右移 
				for (temp=posEnd;temp!=a.end();temp++) {//从起始位后面一位开始找 
					if (*temp=='(') cnt++;	//遇到(叠加计数器+1 
					if (*temp==')') cnt--;	//遇到)抵消计数器-1 
					if (cnt==0) break;		//匹配结束，退出 
				}
				posEnd=temp;	//把所要删除的终止位赋值给posEnd 
				posEnd++;	
				temp=posEnd;
				if (temp==a.end()) 	//下一次操作后光标的重定位
					it--;	//如果所要删除的终止位后面是NULL，就定位到之前起始位前面一位
					else it=temp;	//否则就定位到所要删除的终止位后面一位 
				for (temp=posBeg;temp!=posEnd;)	//删 
					a.erase(temp++);
			}
			else if (*it==')') {	//D指令判断是否右括号 
				posBeg=it;	
				posEnd=it;	//所要删除的终止位在当前位置 
				posBeg--;
				int cnt=1;	//当前位置为)所以要向左移 
				for (temp=posBeg;temp!=a.begin();temp--) {//从终止位前面一位开始找	
					if (*temp==')') cnt++;	//遇到)叠加计数器+1 
					if (*temp=='(') cnt--;	//遇到(抵消计数器-1 
					if (cnt==0) break;		//匹配结束，退出 
				}
				posBeg=temp;	//把所要删除的起始位赋值给posBeg 
				posEnd++;
				temp=posEnd;
				if (temp==a.end()) {//下一次操作后光标的重定位
					it=posBeg; 
					it--;	//如果所要删除的终止位后面是NULL，就定位到之前起始位前面一位
				}
					else it++;	//否则就定位到所要删除的终止位后面一位 
				for (temp=posBeg;temp!=posEnd;)	//删
					a.erase(temp++);
			}
		}
	}
	temp=a.begin();
	temp++;					//第一位是围栏 
	for (it=temp;it!=a.end();it++) 	
		cout<<*it;
	return 0;
}

花絮&起因

由于Titan让我做翻译&做测试数据
于是我生产了以下不忍直视的随机数生成程序

好玩の随机数

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
#include<bits/stdc++.h>
using namespace std;
int main()
{
	srand((int)time(0));
	int n,m,p;

	n=rand()%250;
	n*=2;
	m=rand()%100;
	m*=2;
//	n=rand()%250000;
//	n=n*2;
//	m=rand()%250000;
//	m=m*2;
	p=rand()%n;
	cout<<n<<' '<<m<<' '<<p<<endl;
	int cnt;
	string s;
	do {
		cnt=0;
		s="";
		for (int i=1;i<=n;i++) {
			char c;
			c='('+rand()%2;
			if (c=='(') cnt++;
				else cnt--;
			if (cnt==-1) {
				cnt+=2;
				c='(';
			}
			s=s+c;
		} 
	}while (cnt!=0);
	cout<<s<<endl;
	//直到找到匹配的括号位置（懒人方法） 
	for (int i=1;i<=m;i++) {
		int k=rand()%3;
		if (k==0) cout<<"L";
			else if (k==1) cout<<"R";
				else cout<<"D";
	}
	//并没有判定迭代器是否飞出去 	
	cout<<endl;
	return 0;
}

心得&解释

  • 题目很长，翻译成中文1100字，不过废话很多。
  • 狠狠地体验了迭代器的运用。并使用了对头部和尾部的特殊操作。
  • coding完之后，过了样例以后有点开心，交上去TLE的绝望。之后想挣扎，把整个程序写了个注释，还是没有AC。之后询问了某位大佬，他告诉我是迭代器失效的问题。（虽然这个问题我在前面部分尽力规避了，但还是在最后erase的部分出了岔子。把for()中的递增语句移到循环体中，就可以防止迭代器失效的问题。）
  • 在制作数据的过程中，学到了随机数、文件读写的运用。难点是括号部分完全匹配以及题中的三个指令使得指针不越界。我在随机数生成程序中完成了用循环强制进行括号匹配，由于我源代码的特性，使得指针越界操作直接使程序无法运行，可以保证生成的指令序列合法。