2019.8.2 集训解题报告

考试

  • 考的非常好,$\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$
Your browser is out-of-date!

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

×