2016年9月6日 星期二

校內初賽

今天比了校內的資訊能力競賽初賽
考前還很緊張怕被刷下來
結果發現好像滿水的(x
包括亂入(?)的兩個人我是第六名
然後如果我知道std有binary_search的話就有第三名QwQ
出題者破台 超電(?

pA http://tioj.infor.org/problems/1544
太水了懶得說(?
一開始這題直接丟了個87分
後來想說剩下13分等等有空再弄就先去pB了

pB http://tioj.infor.org/problems/1547
還是很水(?
所以還是懶得說(?

pC http://tioj.infor.org/problems/1809
就是這題超討厭
因為二分寫錯就只有26分= =
然後爆搜好像都有37分..

也不難 把每個握手(讓a<=b)push到一個vector<pair<int,int>>裡面
然後sort 然後二分搜就可以過了

pD http://tioj.infor.org/problems/1546
這題比較開心(?
給你第一排跟第一列 說每個人一次可以填一格新的數字(必須=左上XOR左XOR上) 或是劃出一條p<=len<=q的遞增子序列(不能重複劃) 問誰會沒有操作可以做
基本上因為已經給你第一排跟第一列了 所以整個方格都是確定的
所以有幾個遞增子序列也是固定的 所以只要數一下然後%玩家就可以過了

不過這圖如果完整的開完整個圖的話會MLE
所以一開始就只拿91分而已
後來想到因為你只需要上一條跟這一條的第一個就可以完整的生出這一條
所以就開一個[2][m]的陣列然後交叉掃過去
數那一行有幾個遞增的時候再生就好了
然後就過了

這題其實卡最久的是我以為要嚴格遞增((

pE http://tioj.infor.org/problems/1907
好像是DAG的最長路徑之類的
然後就TLE了最後兩筆 只有60分
所以我也不知道怎麼解(?
大概知道有個地方可以優化一下 不過目前還沒有實作的靈感##

pF http://tioj.infor.org/problems/1613
完全沒想法(O

簡單來說就算是這麼長的文我還是只有一題可以提供code XDD
pD下收 
  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
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define ll long long
#define ld long double
#define PB(x) push_back(x)
#define MP(x,y) make_pair(x,y)
#define vint vector<int>
#define pii pair<int,int>
#define rz(x) resize(x)
#define X first
#define Y second
// #define m (l+r)/2
// #define xm (x1+x2)/2
// #define ym (y1+y2)/2
#define DE cout<<"de"<<endl;

inline int rit(){
    int t=0,k=1;
    char c;
    do{
        c=getchar();
        if(c=='-')k=-1;
    }while(c<'0'||c>'9');
    do{
        t=t*10+c-'0';
        c=getchar();
    }while(c>='0'&&c<='9');
    return t*k;
};

int n,m,p,q;
int mp1[10003],mp2[10003],w[2][10003];
ll act;

int main(){
    n=rit(),m=rit(),p=rit(),q=rit();
    for(int i=0;i<m;i++){
        mp1[i]=rit();
    }
    for(int i=1;i<m;i++){
        mp2[i]=rit();
    }
    mp2[0]=mp1[0];
    act=(m-1)*(m-1);

    int i,j,k;
    for(i=0;i<m;i++){
            if(i){
                w[i&1][0]=mp2[i];
                for(int rr=1;rr<m;rr++){
                    w[i&1][rr]=w[(i+1)&1][rr-1]^w[(i+1)&1][rr]^w[i&1][rr-1];
                }
            }
            else{
                for(int rr=0;rr<m;rr++){
                    w[i&1][rr]=mp1[rr];
                }
            }
        for(j=0;j<m;j=k){
            for(k=j+1;k<m && w[i&1][k]>=w[i&1][k-1];k++){

            }
            int len=k-j;
            if(len>=p){
                if(len>=p && p==q){
                    act+=len-(p-1);
                }
                else if(len>=p && len<=q){
                    len-=(p-1);
                    act+=len*(len+1)/2;
                }
                else{
                    int mlen=len-(p-1);
                    int xlen=len-(q-1);
                    act+=(mlen+xlen)*(mlen-xlen+1)/2;
                }
            }
        }
    }
    
    memset(w,0,sizeof(w));
    for(i=0;i<m;i++){
            if(i){
                w[i&1][0]=mp1[i];
                for(int rr=1;rr<m;rr++){
                    w[i&1][rr]=w[(i+1)&1][rr-1]^w[(i+1)&1][rr]^w[i&1][rr-1];
                }
            }
            else{
                for(int rr=0;rr<m;rr++){
                    w[i&1][rr]=mp2[rr];
                }
            }
        for(j=0;j<m;j=k){
            for(k=j+1;k<m && w[i&1][k]>=w[i&1][k-1];k++){

            }
            int len=k-j;
            if(len>=p){
                if(len>=p && p==q){
                    act+=len-(p-1);
                }
                else if(len>=p && len<=q){
                    len-=(p-1);
                    act+=len*(len+1)/2;
                }
                else{
                    int mlen=len-(p-1);
                    int xlen=len-(q-1);
                    act+=(mlen+xlen)*(mlen-xlen+1)/2;
                }
            }
        }
    }

    printf("%d\n",act%n);
}

為什麼它可以把#define 跟#include 變成註解的顏色=w=
還我還要自己改 而且改完才發現一坨綠的好醜(#
張貼者： 於

沒有留言:

張貼留言

訂閱： 張貼留言 (Atom)