2019.8.2 集训解题报告
浏览 51 | 评论 0 | 字数 6973
Snowflake_Pink
2019年08月02日
  • 考试

    • 考的非常好,$\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$ 了(然而我菜得并没有想下去)。

    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 。

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

    $$ 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​ 翻译了一下

    AVOGADRO

    $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$
    本文作者:Snowflake_Pink
    本文链接:https://snowflake.pink/archives/70/
    最后修改时间:2020-04-13 11:34:25
    本站未注明转载的文章均为原创,并采用 CC BY-NC-SA 4.0 授权协议,转载请注明来源,谢谢!
    评论
    评论会由可爱的 AI 来审核鸭~
    textsms
    支持 Markdown 语法
    email
    link
    评论列表
    暂无评论