2019.8.2 集训解题报告

集训
1662 Words 被浏览 次

考试

  • 考的非常好，$\Leftarrow$ 放屁

佳肴

原来想写个 $dp$ ，磕了大半小时，然后还是决定去打暴力。

$Test’s$ $Code$：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
35
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
const int MAXN=105;
const int INF=2e9;
int s[MAXN],k[MAXN];
int n,ans=INF,Min=INF,Mini;
bool flag=false;
void dfs (int cnt,int ls,int lk){
	if (cnt>n){
		if (!flag) ans=min(ans,Min);
		else ans=min(ans,abs(ls-lk));
		return;
	}
	bool last=flag;
	flag=true;
	dfs (cnt+1,ls*s[cnt],lk+k[cnt]);
	flag=last;
	dfs (cnt+1,ls,lk);
	return;
}
int main(){
	scanf ("%d",&n);
	for (int i=1;i<=n;i++){
		 scanf ("%d%d",&s[i],&k[i]);
		 if (Min>abs(s[i]-k[i])){
		 	Min=abs(s[i]-k[i]);
		 	Mini=i;
		 }
	}
	dfs (1,1,0);
	printf ("%d\n",ans);
	return 0;
}

取数游戏

我似乎除了简单的背包 $dp$ ，其他的就没对过。

是 $COCI$ 的一道原题，围成一个环了大概就能想到区间 $dp$ 了（然而我菜得并没有想下去）。

IVANA

  • 下面大约是上面的翻译

先手拿完第一个数字以后（当然，第一个需要枚举），这个圆圈就可以被拆成一条链，这样就可以区间 $dp$ 了。每次两个人从这一条链的两端取数。

然后设计初始状态：$f[a][b]$ 表示这条链从第 $a$ 个到第 $b$ 个这个区间取数时，（先手能比后手）当前选数选手最多超过另一个人多少（可能会变成负数）。

然后，就可以考虑转移。对于 $f[a][b]$ ，取了 $a$ ，需要一个 $f[a+1][b]$ ；取了 $b$ ，需要一个 $f[a][b-1]$ 。这就是对应的子问题。

对于初始状态，这也十分简单。最小的子问题是 $f[i][i]$ ，因为奇数得分，偶数不得分。所以说当 $i$ 是一个奇数时，初值为 1 ，如果是偶数，那么就为 0 。

那么转移方程就很明显了：

  • 应该用记忆化搜索比较方便吧~

$Fixed$ $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
#include <iostream>
#include <cstdio>

using namespace std;
const int MAXN = 1e2+5;

int f[2*MAXN][2*MAXN], n, a[MAXN], ans;

int main() {
	scanf ("%d",&n);
	for (int i=1; i<=n; i++) {
		int t;
		scanf ("%d",&t);
		t = t % 2;
		f[i][i] = f[i + n][i + n] = t;
	}
	
	for (int k=2; k<=n; k++) {
		for (int i=1; i<=2*n; i++) {
			int j = i+k-1;
			if ( j > 2*n ) break;
			f[i][j] = max(f[i][i] - f[i + 1][j], f[j][j] - f[i][j - 1]);
		}
	}
	
	for (int i=1; i<=n; i++) {
		if ( f[i][i] - f[i+1][i+n-1] > 0 ) ans++;
	}
	printf ("%d\n",ans);
	return 0;
}
  • 去学了下码风，好像码风和打字速度有关…..
  • 今天才发现一个很基础的错误，如果 if 中是负数，也是真，我一直以为是假 $qwq$

官方 $COCI$ 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
#include <stdio.h>
#define MAXN 100
int max( int a, int b ) { return a>b ? a : b; }
int main()
{
   int n, i, L;
   static int f[2*MAXN][2*MAXN];
   int rj;
   scanf( "%d", &n );
   for ( i=0; i<n; ++i ) {
      int x;
      scanf( "%d", &x );
      x %= 2;
      f[i+n][i+n] = f[i][i] = x;
   }
   for ( L=2; L<=n; ++L )
      for ( i=0; i<2*n; ++i ) {
         int j = i+L-1;
         if ( j>=2*n ) break;
         f[i][j] = max( f[i][i] - f[i+1][j], f[j][j] - f[i][j-1] );
      }
   rj = 0;
   for ( i=0; i<n; ++i )
      if ( f[i][i] - f[i+1][i+n-1] > 0 )
         ++rj;
   printf( "%d\n", rj );
   return 0;
}

删除

依然要删完行之后，每列所包含的数都是一样的，因为第一行每个数都只有一个，所以不会出现删完后会有相同的数的情况。所以每次扫一遍，没有出现的数添加到一个队列，然后删，然后如此反复，直到扫不出来。

这里还可以加一个优化，就是再读入每行数据的时候，把每个数在哪一列的位置记录下来，这样删除的就会比较快，不用再扫一遍了。

这道题选自 $COCI$2008 ，去官网把官方题解找到了，然后又去 Google​ 翻译了一下

AVOGADRO

$Fixed$ $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
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
const int MAXN=1e5+5;
int a[3][MAXN],n,ans,cnt[3][MAXN];
int queue[MAXN],head=1,tail;
bool del[MAXN];
vector <int> p[3][MAXN];
inline bool check(){
	int bz=tail;
	for (int i=1;i<=n;i++){
		if (del[p[0][i][0]]) continue;
		bool flag=false;
		for (int j=0;j<3;j++){
			if (cnt[j][i]==0)
				flag=true;
		}
		if (flag) queue[++tail]=i;
	}
	return bz!=tail;
}
int main(){
	scanf ("%d",&n);
	for (int i=0;i<3;i++){
		for (int j=1;j<=n;j++){
			scanf ("%d",&a[i][j]);
			cnt[i][a[i][j]]++;
			p[i][a[i][j]].push_back(j);
		}
	}
	while (check()){
		for (int i=head;i<=tail;i++){
			int num=queue[i];
			for (int j=0;j<3;j++){
				for (int k=0;k<p[j][num].size();k++){
					int l=p[j][num][k];
					if (del[l]) continue;
					ans++;
					del[l]=true;
					cnt[0][a[0][l]]--;
					cnt[1][a[1][l]]--;
					cnt[2][a[2][l]]--;
				}
			}
		}
		head=tail+1;
	}
	printf ("%d\n",ans);
	return 0;
}
  • 我的不是很优雅，用了 $vector$ ，刚好可以用 $vector$ 的动态优势满足空间复杂度

官方 $COCI$ 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
#include <cstdio>
#include <stack>
#include <vector>
#define MAX 100000
using namespace std;
int n;
int a[3][MAX];
int erased[MAX];
vector<int> columns[MAX];
int freq[MAX][3];
stack<int> jobs;
int main( void ) {
   scanf( "%d", &n );
   for( int r = 0; r < 3; ++r ) 
      for( int c = 0; c < n; ++c ) {
         scanf( "%d", &a[r][c] ); --a[r][c];
         columns[a[r][c]].push_back( c );
         ++freq[a[r][c]][r];
      }
   for( int i = 0; i < n; ++i ) 
      if( freq[i][1] == 0 || freq[i][2] == 0 ) 
         jobs.push( i );      
   int ret = 0;
   while( !jobs.empty() ) {
      int number = jobs.top();
      jobs.pop();
      for( vector<int>::iterator it = columns[number].begin(); it != columns[number].end(); ++it ) {
         if( erased[*it] ) continue;
         erased[*it] = 1;
         ++ret;
         if( --freq[a[0][*it]][0] == 0 ) jobs.push( a[0][*it] );
         if( --freq[a[1][*it]][1] == 0 ) jobs.push( a[1][*it] );
         if( --freq[a[2][*it]][2] == 0 ) jobs.push( a[2][*it] );
      }
   }
   printf( "%d\n", ret );
   return 0;
}
  • 很强，但是好像也用了 $vector$ QAQ

区间

这道题思路挺简单的，就是把每个区间的左端点都从大到小排个序。这样，就可以求由右端点组成的序列的最长不下降子序列了，长度就是答案。

但是我的二分挂了，然后还有一个细节，在排序的时候，如果两左端点相同，右端点要从小到大排序，这样才能让之后的最长不下降子序列最长。

细节比较多，最长上升和最长不下降的二分是不一样的，所以以后这种 $O(n \log n)$ 的优化最好用数据结构优化，使用树状数组，虽然有点麻烦，但是至少不会错。

$Test’s$ $Code$：10%

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
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN=1e5+5;
struct node {
	int l,r;
}a[MAXN];
int n;
int s[MAXN],top;
bool cmp (node a,node b){
	return a.l>b.l;
}
int main(){
	scanf ("%d",&n);
	for (int i=1;i<=n;i++){
		scanf ("%d%d",&a[i].l,&a[i].r);
	}
	sort (a+1,a+n+1,cmp);
	for (int i=1;i<=n;i++){
		int t=a[i].r;
		if (t>=s[top]) s[++top]=t;
		else {
			int l=1,r=top,mid;
			while (l<r-1){
				mid=(l+r)/2;
				if (s[mid]>t) r=mid-1;
				else l=mid;
			}
			if (l!=r)
				if (s[r]<=t){
					s[r]=t;
					continue;
				}
			s[l]=t;
		}
	}
	printf ("%d\n",top);
	return 0;
}

$Fixed$ $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
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN=1e5+5;
const int INF=2e9;
struct node {
	int l,r;
}a[MAXN];
int n;
int s[MAXN],top;
bool cmp (node a,node b){
	if (a.l==b.l) return a.r<b.r;
	return a.l>b.l;
}
int main(){
	scanf ("%d",&n);
	for (int i=1;i<=n;i++){
		scanf ("%d%d",&a[i].l,&a[i].r);
	}
	sort (a+1,a+n+1,cmp);
	for (int i=1;i<=n;i++){
		int t=a[i].r;
		if (t>=s[top]) s[++top]=t;
		else {
			int l=1,r=top,mid;
			while (l<=r){
				mid=(l+r)/2;
				if (s[mid]<=t) l=mid+1;
				else r=mid-1;
			}
			s[l]=t;
		}
	}
	printf ("%d\n",top);
	return 0;
}
  • 这题也是 $COCI$ 的，但是我没有翻到 $qwq$
DFS深度优先搜索, DP动态规划, 二分查找, 基础
2019.5.3&4高中部集训
软件-Proxyee Down
关注我

链接

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×