2019.8.2 集训解题报告 - 粉粉何所似？

考试

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

佳肴

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

Test's

Code

：AC

#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$ 了（然而我菜得并没有想下去）。

下面大约是上面的翻译

先手拿完第一个数字以后（当然，第一个需要枚举），这个圆圈就可以被拆成一条链，这样就可以区间 $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 。

那么转移方程就很明显了： f[i][j]=max {f[i][i]-f[i+1][j],f[j][j]-f[i][j-1]}

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

Fixed

Code

：100%

#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

#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 翻译了一下~~

Fixed

Code

：100%

#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：

#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%

#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

：100%

#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$