$$2015-2016\ ACM-ICPC,\ NEERC,\ Northern\ Subregional\ Contest$$

\(A.Alex\ Origami\ Squares\)

签到

//#pragma comment(linker, "/STACK:1024000000,1024000000")

#include<bits/stdc++.h>

using namespace std;

int main(){

    int a,b;

    freopen("alex.in","r",stdin);

    cin >> a >> b;

    freopen("alex.out","w",stdout);

    double res = max(max(min(a/3.0,b/1.0),min(a/1.0,b/3.0)),min(a/2.0,b/2.0));

    cout << res << endl;

    return 0;

}

\(B.Black\ and\ White\)

构造，把多的框在少的里面即可

//#pragma comment(linker, "/STACK:1024000000,1024000000")

#include<bits/stdc++.h>

using namespace std;

function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};

const int MAXN = 1e5+7;

int n,m,len;

char tile[MAXN][5];

int main(){

    #ifdef ONLINE_JUDGE

    freopen("black.in","r",stdin);

    #endif

    ____();

    cin >> n >> m;

    #ifdef ONLINE_JUDGE

    freopen("black.out","w",stdout);

    #endif

    if(m==0){

        cout << 1 << ' ' << 1 << endl << '@' << endl;

        return 0;

    }

    if(n==0){

        cout << 1 << ' ' << 1 << endl << '.' << endl;

        return 0;

    }

    char x='@',y='.';

    if(n<m){

        swap(n,m);

        swap(x,y);

    }

    len = 1;

    if(n>m){

        tile[len][1] = tile[len][2] = tile[len][3] = y;

        len++, m--;

    }

    while(n>m){

        tile[len][2] = x;

        tile[len][1] = tile[len][3] = y;

        len++, n--;

        tile[len][1] = tile[len][2] = tile[len][3] = y;

        len++;

    }

    while(n){

        tile[len][1] = tile[len][2] = tile[len][3] = x;

        len++, n--;

        tile[len][1] = tile[len][2] = tile[len][3] = y;

        len++;

    }

    if(tile[len][1]=='\0') len--;

    cout << len << ' ' << 3 << endl;

    for(int i = 1; i <= len; i++) cout << (tile[i]+1) << endl;

    return 0;

}

\(C.Concatenation\)

答案就是总数量-右串从\(1\)到\(lenr-1\)各个字符在左串\(2~lenl\)之间出现的次数

//#pragma comment(linker, "/STACK:1024000000,1024000000")

#include<bits/stdc++.h>

using namespace std;

function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};

const int MAXN = 3e5+7;

char s[MAXN],t[MAXN];

int len1,len2;

int main(){

    #ifdef ONLINE_JUDGE

    freopen("concatenation.in","r",stdin);

    #endif

    scanf("%s %s",s+1,t+1);

    #ifdef ONLINE_JUDGE

    freopen("concatenation.out","w",stdout);

    #endif

    len1 = strlen(s+1);

    len2 = strlen(t+1);

    int_fast64_t res = len1*(int_fast64_t)len2;

    map<char,int> mp;

    for(int i = 2; i <= len1; i++) mp[s[i]]++;

    for(int i = 1; i < len2; i++) res -= mp[t[i]];

    cout << res << endl;

    return 0;

}

\(D.Distribution\ in\ Metagonia\)

考虑构造时先把质因子\(2\)，\(3\)提出来，然后得到一个奇数，把奇数拆分为\(3^k·p\)，继续对\(p\)拆分直到\(p\)的因子只含\(2\)和\(3\)为止

递归构造即可

//#pragma comment(linker, "/STACK:1024000000,1024000000")

#include<bits/stdc++.h>

using namespace std;

function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};

using LL = int_fast64_t;

int t;

LL n[1111];

void gao(LL m, LL mul, vector<LL> &vec){

    if(m==1){

        vec.emplace_back(mul);

        return;

    }

    if(m%3!=0&&m%2!=0){

        LL tp = 1;

        while(tp*3<=m) tp *= 3;

        gao(tp,mul,vec);

        gao(m-tp,mul,vec);

        return;

    }

    LL sum = 1;

    while(m%2==0){

        sum *= 2;

        m >>= 1;

    }

    while(m%3==0){

        sum *= 3;

        m /= 3;

    }

    gao(m,sum*mul,vec);

}

void solve(LL m){

    vector<LL> vec;

    gao(m,1,vec);

    cout << vec.size() << endl;

    for(LL x : vec) cout << x << ' '; cout << endl;

}

int main(){

    #ifdef ONLINE_JUDGE

    freopen("distribution.in","r",stdin);

    freopen("distribution.out","w",stdout);

    #endif

    ____();

    cin >> t;

    for(int i = 1; i <= t; i++) cin >> n[i];

    for(int i = 1; i <= t; i++) solve(n[i]);

    return 0;

}

\(E.Easy\ Arithmetic\)

打记号标记前导零、上一位是否是符号、当前正负值然后判断即可

//#pragma comment(linker, "/STACK:1024000000,1024000000")

#include<bits/stdc++.h>

using namespace std;

function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};

const int MAXN = 3333;

char s[MAXN],tar[MAXN];

int main(){

    #ifdef ONLINE_JUDGE

    freopen("easy.in","r",stdin);

    #endif

    ____();

    cin >> (s+1);

    int len = strlen(s+1);

    #ifdef ONLINE_JUDGE

    freopen("easy.out","w",stdout);

    #endif

    int c = 1, ptr = 1;

    bool tag = true, lead = true, op = true;

    while(ptr<=len){

        if(!isdigit(s[ptr])){

            if(s[ptr]=='-') tag = false;

            else if(s[ptr]=='+') tag = true;

            tar[c++] = s[ptr];

            op = true;

        }

        else{

            if(op){

                op = false;

                tar[c++] = s[ptr];

                lead = (s[ptr]=='0');

            }

            else{

                if(!tag){

                    tar[c++] = '+';

                    tag = true;

                    tar[c++] = s[ptr];

                    lead = (s[ptr]=='0');

                }

                else{

                    if(lead){

                        tar[c++] = '+';

                        lead = (s[ptr]=='0');

                        tar[c++] = s[ptr];

                    }

                    else tar[c++] = s[ptr];

                }

            }

        }

        ptr++;

    }

    cout << (tar+1) << endl;

    return 0;

}

\(F.Fygon\)

\(G.Graph\)

友情链接

大顶堆小顶堆维护，做法有点妙

//#pragma comment(linker, "/STACK:1024000000,1024000000")

#include<bits/stdc++.h>

using namespace std;

function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};

const int MAXN = 1e5+7;

int n,m,k,pre,ord[MAXN],cur,deg[MAXN];

vector<int> G[MAXN];

set<int> S;

set<int,greater<int>> done;

vector<pair<int,int>> edge;

void toposort(int u){

    ord[++cur] = u;

    pre = u;

    for(int v : G[u]) if(--deg[v]==0) S.insert(v);

}

int main(){

    #ifdef ONLINE_JUDGE

    freopen("graph.in","r",stdin);

    freopen("graph.out","w",stdout);

    #endif

    scanf("%d %d %d",&n,&m,&k);

    for(int i = 1; i <= m; i++){

        int u, v;

        scanf("%d %d",&u,&v);

        G[u].emplace_back(v);

        deg[v]++;

    }

    for(int i = 1; i <= n; i++) if(deg[i]==0) S.insert(i);

    while(cur<n){

        if(S.empty()){          //自己安排下一个节点顺序

            int u = *done.begin();

            done.erase(u);

            edge.emplace_back(make_pair(pre,u));

            toposort(u);

        }

        else if(!k||(S.size()==1&&(done.empty()||*S.begin()>*done.begin()))){

            int u = *S.begin();

            S.erase(u);

            toposort(u);

        }

        else{

            k--;

            done.insert(*S.begin());

            S.erase(S.begin());

        }

    }

    for(int i = 1; i <= n; i++) printf("%d ",ord[i]); puts("");

    printf("%d\n",edge.size());

    for(auto p : edge) printf("%d %d\n",p.first,p.second);

    return 0;

}

\(H.Hash\ Code\ Hacker\)

每次从后一位向前进一位，后一位\(y\)变成\(Z\)，前一位的\(x\)变成\(y\)，重复操作即可

//#pragma comment(linker, "/STACK:1024000000,1024000000")

#include<bits/stdc++.h>

using namespace std;

function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};

const int MAXN = 1111;

char s[MAXN];

int k;

int main(){

    #ifdef ONLINE_JUDGE

    freopen("hash.in","r",stdin);

    #endif

    cin >> k;

    #ifdef ONLINE_JUDGE

    freopen("hash.out","w",stdout);

    #endif

    for(int i = 1; i <= 999; i++) s[i] = 'x';

    s[1000] = 'y';

    cout << (s+1) << endl;

    for(int i = 1; i < k; i++){

        s[1000+1-i] = 'Z';

        s[1000-i] = 'y';

        cout << (s+1) << endl;

    }

    return 0;

}

\(I.Insider's\ Information\)

\(J.Journey\ to\ the\ "The World's Start"\)

二分答案之后线段树维护DP求最小耗时

//#pragma comment(linker, "/STACK:1024000000,1024000000")

#include<bits/stdc++.h>

using namespace std;

function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};

const int MAXN = 1e5+7;

using LL = int_fast64_t;

const LL INF = 0x3f3f3f3f3f3f3f3f;

int n,t,p[MAXN],cost[MAXN];

struct SegmentTree{

    LL minn[MAXN<<2];

    int l[MAXN<<2],r[MAXN<<2];

    #define ls(rt) ((rt) << 1)

    #define rs(rt) ((rt) << 1 | 1)

    void pushup(int rt){ minn[rt] = min(minn[ls(rt)],minn[rs(rt)]); }

    void build(int L, int R, int rt){

        l[rt] = L, r[rt] = R;

        if(L+1==R) return;

        int mid = (L+R) >> 1;

        build(L,mid,ls(rt)); build(mid,R,rs(rt));

        pushup(rt);

    }

    void update(int pos, int rt, LL x){

        if(l[rt]+1==r[rt]) {

            minn[rt] = x;

            return;

        }

        int mid = (l[rt]+r[rt]) >> 1;

        if(pos<mid) update(pos,ls(rt),x);

        else update(pos,rs(rt),x);

        pushup(rt);

    }

    LL qmin(int L, int R, int rt){

        if(l[rt]>=R||L>=r[rt]) return INF;

        if(L<=l[rt] && r[rt]<=R) return minn[rt];

        return min(qmin(L,R,ls(rt)),qmin(L,R,rs(rt)));

    }

}ST;

bool check(int mid){

    ST.update(1,1,-1);

    for(int i = 2; i <= n; i++) ST.update(i,1,ST.qmin(max(1,i-mid),i,1)+cost[i]);

    return ST.qmin(n,n+1,1)+n<=t;

}

int solve(){

    int l = 1, r = n-1;

    ST.build(1,n+1,1);

    while(l<=r){

        int mid = (l+r)>>1;

        if(check(mid)) r = mid - 1;

        else l = mid + 1;

    }

    return p[l];

}

int main(){

    #ifdef ONLINE_JUDGE

    freopen("journey.in","r",stdin);

    freopen("journey.out","w",stdout);

    #endif

    scanf("%d %d",&n,&t);

    for(int i = 1; i < n; i++) scanf("%d",&p[i]);

    for(int i = n-2; i >= 1; i--) p[i] = min(p[i],p[i+1]);

    for(int i = 2; i < n; i++) scanf("%d",&cost[i]);

    printf("%d\n",solve());

    return 0;

}

\(K.Kingdom\ Trip\)

\(L.Lucky\ Chances\)

签到，暴力

//#pragma comment(linker, "/STACK:1024000000,1024000000")

#include<bits/stdc++.h>

using namespace std;

function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};

const int MAXN = 111;

const int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};

int n,m,A[MAXN][MAXN];

int main(){

    #ifdef ONLINE_JUDGE

    freopen("lucky.in","r",stdin);

    #endif

    ____();

    cin >> n >> m;

    for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) cin >> A[i][j];

    #ifdef ONLINE_JUDGE

    freopen("lucky.out","w",stdout);

    #endif

    int res = 0;

    for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++){

        for(int d = 0; d < 4; d++){

            bool ok = true;

            for(int x = i+dir[d][0], y = j + dir[d][1]; x>0&&x<=n&&y>0&&y<=m; x+=dir[d][0],y+=dir[d][1]) if(A[x][y]>=A[i][j]) ok = false;

            res+=ok;

        }

    }

    cout << res << endl;

    return 0;

}

最新文章

  1. AnguarJS 第一天----Hello World
  2. 关于Windows 7启动后网络一直转的问题的一个解决方法
  3. ln
  4. 这些年我们一起搞过的持续集成~Jenkins+Perl and Shell script
  5. linux-2 下tomcat重启定向输出日志
  6. javascript滚动条之ScrollBar.js
  7. sourceforge.net 打不开怎么办？（转）
  8. Linux下信号的简单使用
  9. Git fetch和git pull的区别(转)
  10. HomeSnap
  11. 从字节理解Unicode（UTF8/UTF16)
  12. JS~JS里的数据类型
  13. golang（2）：beego 环境搭建
  14. phabricator在mac上的搭建(转)
  15. POJ 3278 Catch That Cow（模板——BFS）
  16. Android 结合实际项目学会ListView局部刷新和相关知识《一》
  17. ABP学习笔记总汇
  18. Web 录音
  19. IDEA 根据 Mysql 自动生成
  20. python标准库大全(转)

热门文章

  1. 了解一下RPC，为何诞生RPC，和HTTP有什么不同？
  2. 工具用的好，下班回家早！5分钟玩转iTerm2！
  3. LeetCode234 回文链表
  4. 牛客网NC15二叉树的层次遍历
  5. Nginx 实现动态负载均衡(Nginx-1.10.1 + Consul v0.6.4)
  6. Centos 6.5 Rabbitmq 安装和集群,镜像部署
  7. Memcached repcached 高可用
  8. linux最大打开文件句柄数
  9. SDUST数据结构 - chap7 图
  10. 基于kubernetes实现coredns的及验证