2017 Multi-University Training Contest – Team 9 1008

类型:模拟
瞎搞,优化暴力.关键在于理解题意,我还是把它归在模拟吧.
题目连接: :earth_americas:HDU-6168 Numbers

github Code Link: :earth_asia:1008.cpp
Test Code: :earth_asia:1008test.cpp

题解: 用map记录下每个数字出现的次数.然后对b进行排序,首先可以知道,排序后的数组,前两个数一定是a序列的前两个数.然后从这两个数开始拓展,a1+a2必在b中,所以在map中找到a1+a2的数量然后-1,之后把接下来的第一个数Push到a数组中,并且删除一个a1+a3和a2+a3,依次递推.知道a.size()到达sqrt(m/2)或者i>=m为止,结束循环.

Code:

#include<bits/stdc++.h>
using namespace std;
const int maxn=200000;

int c[maxn];
int m,n;
map<int,int> d;
vector<int> a;
int main(){
    while(~scanf("%d",&m)){
        d.clear();a.clear();
        n=sqrt(m<<1);
        for(int i=0;i<m;++i){
            scanf("%d",&c[i]);
            d[c[i]]++;
        }
        sort(c,c+m);
        a.push_back(c[0]);a.push_back(c[1]);
        d[c[1]]--;d[c[0]]--;
        for(int i=1;i<m && a.size()<n;++i){
            int si=a.size()-1;
            for(int j=0;j<si;++j){
                if(d.find(a[si]+a[j])!=d.end() && d[a[si]+a[j]]>0){
                    d[a[si]+a[j]]--;
         //           printf("IDone %d\n",a[si-1]+a[j]);
                }
            }
            while(d[c[i]]==0){
                int no=c[i];
                while(c[i]==no){
                    ++i;
                    if(i>=m)break;
                }
                if(i>=m)break;
    //            printf("Done %d\n",c[i]);
            }
            if(i<m){
                a.push_back(c[i]);
         //       printf("Push %d\n",c[i]);
                d[c[i]]--;
            }
            --i;
        }
        printf("%d\n",a.size());
        printf("%d",a[0]);
        for(int i=1;i<a.size();++i){
            printf(" %d",a[i]);
        }
        printf("\n");
    }
    return 0;
}

Test Code:

#include<bits/stdc++.h>
using namespace std;
int t[5]={3,7,6,9,10};
vector<int> ans;
int main(){
     freopen("in.txt", "r", stdin);
     freopen("out.txt", "w", stdout);
     for(int i=0;i<5;++i) ans.push_back(t[i]);
     for(int i=0;i<5;++i){
        for(int j=i+1;j<5;++j){
            ans.push_back(t[i]+t[j]);
        }
     }
     printf("%d\n",ans.size());
     for(int i=0;i<ans.size();++i) printf("%d ",ans[i]);
    return 0;
}

ccf 2017前四题

第一题官网挂掉了.第五题感觉可以用最大流搞搞.
类型:
第一题:贪心
第二题:链表(我用STL里的list实现的)
第三题:中等模拟?
第四题:并查集+最小堆优化Kruskal
题目连接: **要登录和会员 ** http://118.190.20.162/home.page

github: :earth_africa:CCF 2017-3 前四题

第一题:

#include<cstdio>
#include<cstring>
using namespace std;
int main(){
    int N,K;
    while(~scanf("%d%d",&N,&K)){
        int ans=0,d,n=0;
        for(int i=0;i<N;++i){
            scanf("%d",&d);
            n+=d;
            if(n>=K){
                n=0;
                ans++;
            }
        }
        if(n)ans++;
        printf("%d\n",ans);
    }
    return 0;
}

第二题:

#include<bits/stdc++.h>
using namespace std;

int N,M;
int I,J;

list<int> li;

int main(){
    while(~scanf("%d%d",&N,&M)){
        li.clear();
        for(int i=1;i<=N;++i){
            li.push_back(i);
        }
        for(int i=1;i<=M;++i){
            scanf("%d%d",&I,&J);
            if(J==0)continue;
            list<int>::iterator it,it2;
            for(it=li.begin();*it!=I;it++){}
            it2=it;
            int flag=J>0?1:-1;
            J=abs(J)+(flag>0?1:0);
            while(J){
                J--;
                flag>0?it++:it--;
            }
            li.insert(it,I);
            li.erase(it2);
        }
        list<int>::iterator it;
        it=li.begin();
        printf("%d",*it);
        it++;
        for(;it!=li.end();it++){
            printf(" %d",*it);
        }
        printf("\n");
    }
    return 0;
}

第三题:

#include<bits/stdc++.h>

#define BUF_SS 101

using namespace std;

char buf[101];
int pre=-1;

int check_hl(int st){
    char hr[100];
    string tip;
    int ind=st+1,cs=0,hs=0;
    while(buf[ind]!=']'){
        if(buf[ind]=='_'){
            tip+="<em>";
            ind++;
            while(buf[ind]!='_'){
                tip+=buf[ind];
                ind++;
            }
            tip+="</em>";
            ind++;
        }else{
            tip+=buf[ind];
            ind++;
        }
    }
    ind+=2;
    while(buf[ind]!=')'){
        hr[hs++]=buf[ind];
        ind++;
    }
    hr[hs]='\0';
    printf("<a href=\"%s\">",hr);
    cout<<tip<<"</a>";
    return ind-st;
}

int check_em(int st){
    int ind=st+1;
    printf("<em>");
    while(buf[ind]!='_'){
        if(buf[ind]=='['){
            int ed=check_hl(ind);
            ind+=(ed+1);
        }else{
            putchar(buf[ind]);
            ind++;
        }
    }
    printf("</em>");
    return ind-st;
}

void check_h(int sz){
    int n,r=0;
    char sts[20],ste[20];
    while(buf[r]=='#'){
        r++;
    }
    int s=r,e=sz-1;
    sprintf(sts,"<h%d>",r);
    sprintf(ste,"</h%d>",r);
    for(;buf[s]==' ';s++){}
    printf("%s",sts);
    for(int i=s;buf[i]!='\n';++i){
        int ed=0;
        if(buf[i]=='_') ed=check_em(i);
        else if(buf[i]=='[') ed=check_hl(i);
        else putchar(buf[i]);
        i+=ed;
    }
    printf("%s\n",ste);
}

void check_u(int sz){
    if(pre!=2)printf("<ul>\n");
    int s=1,e=sz-1;
    for(;buf[s]==' ';s++){}
    printf("<li>");
    for(int i=s;buf[i]!='\n';++i){
        int ed=0;
        if(buf[i]=='_') ed=check_em(i);
        else if(buf[i]=='[') ed=check_hl(i);
        else putchar(buf[i]);
        i+=ed;
    }
    printf("</li>\n");
}

void check_p(int sz){
    if(pre!=3)printf("<p>");
    if(pre==3)putchar('\n');
    for(int i=0;buf[i]!='\n' && i<sz;++i){
        int ed=0;
        if(buf[i]=='_') ed=check_em(i);
        else if(buf[i]=='[') ed=check_hl(i);
        else putchar(buf[i]);
        i+=ed;
    }
}

int main(){
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    while(fgets(buf,BUF_SS,stdin)){
        if(buf[0]=='\n'){
            if(pre==3){
                printf("</p>\n");
                pre=0;continue;
            }else if(pre==2){
                printf("</ul>\n");
                pre=0;continue;
            }
            continue;
        }
        int sz=strlen(buf);
        if(buf[0]=='#') check_h(sz),pre=1;
        else if(buf[0]=='*') check_u(sz),pre=2;
        else check_p(sz),pre=3;
    }
    if(pre==3)printf("</p>\n");
    if(pre==2)printf("</ul>\n");
    return 0;
}

写题的时候写了一组测试数据:
In[1]:

# Heading

## Sub-heading

Paragraphs are separated
by a blank line.

Text attributes _italic_.

Bullet list:

*      apples
* oranges
* pears

A _[NLJ6link616lins1](http://example.com)_.

[NLJ6_link_616_lins_1](http://example.com)

out[1]:

<h1>Heading</h1>
<h2>Sub-heading</h2>
<p>Paragraphs are separated
by a blank line.</p>
<p>Text attributes <em>italic</em>.</p>
<p>Bullet list:</p>
<ul>
<li>apples</li>
<li>oranges</li>
<li>pears</li>
</ul>
<p>A <em><a href="http://example.com">NLJ6link616lins1</a></em>.</p>
<p><a href="http://example.com">NLJ6<em>link</em>616<em>lins</em>1</a></p>

第四题:

#include<bits/stdc++.h>
using namespace std;
const int MAX_M=200000+10;
const int maxn=200000+10;
int N,M;
int A,B,C;

struct Edge{
    int from,to,dist;
};
struct HeapNode{
    int d,from,to;
    bool operator<(const HeapNode& rhs)const{
        return d>rhs.d;
    }
};

struct Kruskal{
    int n,m;///点数和边数
    vector<Edge> edges;///边表
    vector<int> G[maxn];///每个节点出发的边编号
    priority_queue<HeapNode> Q;

    ///并查集
    int fa[maxn];///父亲
    int ra[maxn];///高度
    ///init:初始化(点数)
    ///find_Root:查找树的根
    ///unite:合并x和y所属集合
    ///same:判断x和y是否是同一个集合
    void init(int n){
        this->n=n;
        for(int i=0;i<n;++i){
            fa[i]=i;
            ra[i]=0;
            G[i].clear();
        }
        edges.clear();
    }
    int find_Root(int x){
        if(fa[x]==x){
            return x;
        }else{
            return fa[x]=find_Root(fa[x]);
        }
    }
    void unite(int x,int y){
        x=find_Root(x);
        y=find_Root(y);
        if(x==y) return;

        if(ra[x]<ra[y]){
            fa[x]=y;
        }else{
            fa[y]=x;
        }
    }
    bool same(int x,int y){
        return find_Root(x)==find_Root(y);
    }

    void AddEdge(int from,int to,int dist){
        edges.push_back((Edge){from,to,dist});
        m=edges.size()-1;
        G[from].push_back(m-1);
        Q.push((HeapNode){dist,from,to});
    }

    int kruskal(){
        HeapNode h;
        while(!Q.empty()){
            if(find_Root(N)==find_Root(1))break;
            h=Q.top();Q.pop();
            if(find_Root(h.from)==find_Root(h.to))continue;
            unite(h.from,h.to);
        }
        printf("%d\n",h. d);
    }
}K;

int main(){
    while(~scanf("%d%d",&N,&M)){
        K.init(N);
        for(int i=0;i<M;++i){
            scanf("%d%d%d",&A,&B,&C);
            K.AddEdge(A,B,C);
        }
        K.kruskal();
    }
    return 0;
}

2017多校训练1 HDU 6034 Balala Power!

题目连接: :point_right:Balala Power!
Balala

题意: 把26个英文字母看成26进制中的一位,YI一对应起来,给你n个由26个字符组成的字符串,每个字符串代表一个26进制的数,求这n个26进制数的最大的和mod 1e9+7 的结果.注意,可以有前导0,规则是为0的字符不能位于len>1的字符串的开头.

题解: 统计每个字符的总结果,排序,最大的字符赋值25,然后依次往下赋值.然后判断前导0,找到第一个可以为0的存在的字符,将它赋值为0,之后其他的左移一位.(出现前导0的情况表示26个字符都已经出现了).

github:
:point_right:1002.cpp

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
const int mod=1e9+7;
struct star{
    int reg[100005];
    bool vi;
    int c;
    bool operator < (const star &A)const{
        for(int i=maxn-1;i>=0;--i){
            if(reg[i]>A.reg[i]) return 1;
            else if(reg[i]<A.reg[i]) return 0;
            else continue;
        }
    }
}ch[30];
char str[100005];
int Hash[30];///字符-权值映射
long long ans,fac[100005];
inline void init(){
    for(int i=0;i<27;++i){
        memset(ch[i].reg,0,sizeof(ch[i].reg));
        ch[i].vi=true;
        ch[i].c=0;
    }
    ans=0;
}
int main(){
    int n,len,p,kase=0;
    fac[0]=1;///预先处理26^i;
    for(int i=1;i<maxn;++i)
        fac[i]=fac[i-1]*26%mod;
    while(~scanf("%d",&n)){
        init();
        for(int i=0;i<n;++i){
            scanf("%s",str);
            len=strlen(str);
            for(int j=0;j<len;++j){
                p=str[j]-'a';
                ch[p].reg[len-j-1]++;
            }
            if(len>1)
                ch[str[0]-'a'].vi=false;
        }
        for(int i=0;i<26;++i){
            for(int j=0;j<maxn;++j){
                if(ch[i].reg[j]>=26){
                    ch[i].reg[j+1]+=ch[i].reg[j]/26;
                    ch[i].reg[j]%=26;
                }
            }
            ch[i].c=i;
        }
        sort(ch,ch+26);
        for(int i=0;i<26;++i)
            Hash[ch[i].c]=26-i-1;
        for(int i=25;i>=0;--i){///从最小的开始判断是否可以为0
            if(ch[i].vi){
                for(int j=25;j>i;--j)
                    Hash[ch[j].c]=Hash[ch[j-1].c];
                Hash[ch[i].c]=0;
                break;
            }
        }
        for(int i=0;i<26;++i){
            for(int j=0;j<maxn;++j){
                ans=(ans+fac[j]*ch[i].reg[j]*Hash[ch[i].c]%mod)%mod;
            }
        }
        printf("Case #%d: %lld\n",++kase,ans);
    }
    return 0;
}

UVa 10795

【Link】

A Different Task

汉诺塔问题总结:

杭电 汉诺塔问题总结

【题解】

大部分直接写在代码里,6-start[i]-final[i]=1+2+3-start[i]-final[i].因为柱子编号是1,2,3.所以这样减一下得到的是最终该盘所在柱子下标.

f(P,i,final):已知各盘子的初始柱子编号数组为P,把盘子1,2,3,4…i全部移到柱子final所需的步数.

参考局面等于中转态.即中转柱子下标为6-P[i]-finish[i].将前i-1个盘子移动到中转柱上.然后把盘子i移动到final柱子上,最后将i-1个盘子从中转态移动到final.

【Code】

UVA 10795.cpp

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

LL f(int* P,int i,int finaln){
    if(i==0) return 0;
    ///如果当前最大的这个号的起始盘子等于最终落脚盘子
    ///不用移动.所以f(P,i,final)=f(P,i-1,final)
    if(P[i]==finaln) return f(P,i-1,finaln);
    ///经典汉诺塔的结论,将前i-1个盘子从一个柱子移动到另一个柱子
    ///这个步骤需要2^(i-1)-1步.加上移动盘子i到最终盘子
    ///的那一步,一共需要2^(i-1)步.
    return f(P,i-1,1+2+3-P[i]-finaln)+(1LL<<(i-1));
}

const int maxn=60+10;
int n,start[maxn],finish[maxn];

int main(){
    int kase=0;
    while(scanf("%d",&n)==1&&n){
        for(int i=1;i<=n;++i)scanf("%d",&start[i]);
        for(int i=1;i<=n;++i)scanf("%d",&finish[i]); ///结论:如果最大的盘子一开始就在最终的柱子上 ///则不用移动. ///找到号码最大的那几个不需要移动的盘子. int k=n; while(k>=1&&start[k]==finish[k])k--;

        ///结论:由于移动的步数是对称的,即往回移动的步伐
        ///和步数等于往前移动.
        LL ans=0;
        if(k>=1){
            int other=6-start[k]-finish[k];
            ans=f(start,k-1,other)+f(finish,k-1,other)+1;
        }
        printf("Case %d: %lld\n",++kase,ans);
    }
    return 0;
}

LA 3401

【Link】

Colored Cubes,Tokyo 2005,LA 3401

【题解】

思路题,模拟题

先预处理处所有旋转可能.然后通过固定第一个立方体,用于处理出的表来旋转剩下的n-1个立方体.dfs解决,然后对每种旋转情况进行check.更新ans.

【预处理代码及处理结果】

LA 3401旋转情况.cpp

#include<bits/stdc++.h>
using namespace std;

int Dleft[]={4,0,2,3,5,1};
int up[]={2,1,5,0,4,3};

//旋转
void rot(int* T,int* p){
    int q[6];
    memcpy(q,p,sizeof(q));
    for(int i=0;i<6;++i){
        p[i]=T[q[i]];
    }
}

void enumerate_permutations(){
    int p0[6]={0,1,2,3,4,5};
    printf("int dice24[24][6] = {\n");
    for(int i=0;i<6;++i){
        int p[6];
        memcpy(p,p0,sizeof(p0));
        if(i==0) rot(up,p);
        if(i==1) {rot(Dleft,p); rot(up,p);}
        if(i==3) {rot(up,p);rot(up,p);}
        if(i==4) {rot(Dleft,p);rot(Dleft,p);rot(Dleft,p);rot(up,p);}
        if(i==5) {rot(Dleft,p);rot(Dleft,p);rot(up,p);}
        for(int i=0;i<4;++i){
            printf("{%d,%d,%d,%d,%d,%d},\n",p[0],p[1],p[2],p[3],p[4],p[5]);
            rot(Dleft,p);
        }
    }
    printf("};\n");
}

int main(){
    freopen("3401.txt","w",stdout);
    enumerate_permutations();
    return 0;
}

处理结果:

int dice24[24][6] = {
{2,1,5,0,4,3},
{2,0,1,4,5,3},
{2,4,0,5,1,3},
{2,5,4,1,0,3},
{4,2,5,0,3,1},
{5,2,1,4,3,0},
{1,2,0,5,3,4},
{0,2,4,1,3,5},
{0,1,2,3,4,5},
{4,0,2,3,5,1},
{5,4,2,3,1,0},
{1,5,2,3,0,4},
{5,1,3,2,4,0},
{1,0,3,2,5,4},
{0,4,3,2,1,5},
{4,5,3,2,0,1},
{1,3,5,0,2,4},
{0,3,1,4,2,5},
{4,3,0,5,2,1},
{5,3,4,1,2,0},
{3,4,5,0,1,2},
{3,5,1,4,0,2},
{3,1,0,5,4,2},
{3,0,4,1,5,2},
};

【题解代码】

LA 3401.cpp

#include<bits/stdc++.h>
using namespace std;
///旋转情况表
int dice24[24][6] = {
{2,1,5,0,4,3},
{2,0,1,4,5,3},
{2,4,0,5,1,3},
{2,5,4,1,0,3},
{4,2,5,0,3,1},
{5,2,1,4,3,0},
{1,2,0,5,3,4},
{0,2,4,1,3,5},
{0,1,2,3,4,5},
{4,0,2,3,5,1},
{5,4,2,3,1,0},
{1,5,2,3,0,4},
{5,1,3,2,4,0},
{1,0,3,2,5,4},
{0,4,3,2,1,5},
{4,5,3,2,0,1},
{1,3,5,0,2,4},
{0,3,1,4,2,5},
{4,3,0,5,2,1},
{5,3,4,1,2,0},
{3,4,5,0,1,2},
{3,5,1,4,0,2},
{3,1,0,5,4,2},
{3,0,4,1,5,2},
};


const int maxn=4;//最大立方体数
///
///立方体数,第i个立方体原始涂色,dfs后得到的答案
///
int n,dice[maxn][6],ans;

///
///借用vector判断改颜色是否已存在,并借第一个立方体的
///涂颜色的顺序(下标)来决定每个颜色的下标是多少.
///进而确定其他立方体的颜色下标
///
vector names;
int ID(const char* name){
    string s(name);
    int n=names.size();
    for(int i=0;i<n;++i)
        if(names[i]==s) return i;//已存在
    names.push_back(s);
    return n;//不存在,加入后返回
}

///每个立方体的旋转方式和旋转后各个面的颜色
int r[maxn],color[maxn][6];

///每次dfs到n个立方体后,判断所需旋转次数
///然后更新ans
void check(){
    ///对于每个立方体按r[i]旋转
    for(int i=0;i<n;++i)
        for(int j=0;j<6;++j) color[i][dice24[r[i]][j]]=dice[i][j];

    int tot=0;///需要重新涂色的面数
    for(int j=0;j<6;++j){///考虑每个面
        int cnt[maxn*6];///每个面颜色出现的次数
        memset(cnt,0,sizeof(cnt));
        int maxface=0;
        ///记录每个面最多的颜色
        for(int i=0;i<n;++i)
            maxface=max(maxface,++cnt[color[i][j]]);
        tot+=n-maxface;///第j面的最少重涂次数
    }
    ans=min(tot,ans);
}

///把每个面都旋转,旋转不计次数,所以直接判断是否旋转后每个面完全相等即可
void dfs(int d){
    if(d==n) check();
    else{
        for(int i=0;i<24;++i){
            r[d]=i;
            dfs(d+1);
        }
    }
}

int main(){
    while(scanf("%d",&n)==1&&n){
        names.clear();
        for(int i=0;i<n;++i){
            for(int j=0;j<6;++j){
                char name[30];
                scanf("%s",name);
                dice[i][j]=ID(name);
            }
        }
        ans=n*6;///上界,所有面都重涂的结果
        r[0]=0;///第一个立方体不旋转
        dfs(1);
        printf("%d\n",ans);
    }
    return 0;
}

第14届浙江省赛By Tusimple

【网赛链接】

第14届浙江省赛By Tusimple

【A】

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
#define cle(a,val) memset(a,(val),sizeof(a))
#define SI(N) scanf(“%d”,&(N))
#define SII(N,M) scanf(“%d %d”,&(N),&(M))
#define SIII(N,M,K) scanf(“%d %d %d”,&(N),&(M),&(K))
#define rep(i,b) for(int i=0;i<(b);i++)
#define rez(i,a,b) for(int i=(a);i<=(b);i++)
#define red(i,a,b) for(int i=(a);i>=(b);i–)
const ll LINF = 0x3f3f3f3f3f3f3f3f;
#define PU(x) puts(#x);
#define PI(A) cout<<(A)<<endl;
#define DG(x) cout<<#x<<“=”<<(x)<<endl;
#define DGG(x,y) cout<<#x<<“=”<<(x)<<” “<<#y<<“=”<<(y)<<endl;
#define DGGG(x,y,z) cout<<#x<<“=”<<(x)<<” “<<#y<<“=”<<(y)<<” “<<#z<<“=”<<(z)<<endl;
#define PIar(a,n) rep(i,n)cout<<a[i]<<” “;cout<<endl;
#define PIarr(a,n,m) rep(aa,n){rep(bb, m)cout<<a[aa][bb]<<” “;cout<<endl;}
const double EPS = 1e-9 ;
int N,a1,T;
int Kobayashi[4]={1,0,1,-1},Kscore;
int Tohru[4]={0,1,1,-1},Tscore;
int main(){
    while(~SI(N)){
        while(N–){
            SI(T);
            Kscore=0;
            Tscore=0;
            rep(i,T){
                SI(a1);
                Kscore+=Kobayashi[a1-1];
                Tscore+=Tohru[a1-1];
            }
            if(Kscore>Tscore)
                puts(“Kobayashi”);
            else if(Tscore>Kscore)
                puts(“Tohru”);
            else
                puts(“Draw”);
        }
    }
    return 0;
}

【B】

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
#define cle(a,val) memset(a,(val),sizeof(a))
#define SI(N) scanf(“%d”,&(N))
#define SII(N,M) scanf(“%d %d”,&(N),&(M))
#define SIII(N,M,K) scanf(“%d %d %d”,&(N),&(M),&(K))
#define rep(i,b) for(int i=0;i<(b);i++)
#define rez(i,a,b) for(int i=(a);i<=(b);i++)
#define red(i,a,b) for(int i=(a);i>=(b);i–)
const ll LINF = 0x3f3f3f3f3f3f3f3f;
#define PU(x) puts(#x);
#define PI(A) cout<<(A)<<endl;
#define DG(x) cout<<#x<<“=”<<(x)<<endl;
#define DGG(x,y) cout<<#x<<“=”<<(x)<<” “<<#y<<“=”<<(y)<<endl;
#define DGGG(x,y,z) cout<<#x<<“=”<<(x)<<” “<<#y<<“=”<<(y)<<” “<<#z<<“=”<<(z)<<endl;
#define PIar(a,n) rep(i,n)cout<<a[i]<<” “;cout<<endl;
#define PIarr(a,n,m) rep(aa,n){rep(bb, m)cout<<a[aa][bb]<<” “;cout<<endl;}
const double EPS = 1e-9 ;
const int maxn=20000+10;
int T,N,fk,Orz,flag,cnt;
int score[maxn],scomp[maxn];
int main(){
    while(~SI(T)){
        while(T–){
            fill(score,score+4000,0);
            Orz=flag=0;
            SI(N);
            if(N>13 || N<10){
                rep(i,N){
                    SI(fk);
                }
                puts(“No”);continue;
            }
            rep(i,N){
                SI(fk);
                if(fk<=0){
                    flag=1;
                }else{
                    score[fk]++;
                }
                scomp[i]=fk;
            }
            if(flag){
                puts(“No”);
            }else{
                if(score[1]<2){
                    puts(“No”);
                    continue;
                }else{
                    sort(scomp,scomp+N);
                    rez(i,1,N-2){
                        if(scomp[i]-scomp[i-1]>2){
                            puts(“No”);
                            flag=1;
                            break;
                        }
                    }
                    if(!flag) puts(“Yes”);
                }
            }
        }
    }
    return 0;
}

【C】

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
#define cle(a,val) memset(a,(val),sizeof(a))
#define SI(N) scanf(“%d”,&(N))
#define SII(N,M) scanf(“%d %d”,&(N),&(M))
#define SIII(N,M,K) scanf(“%d %d %d”,&(N),&(M),&(K))
#define rep(i,b) for(int i=0;i<(b);i++)
#define rez(i,a,b) for(int i=(a);i<=(b);i++)
#define red(i,a,b) for(int i=(a);i>=(b);i–)
const ll LINF = 0x3f3f3f3f3f3f3f3f;
#define PU(x) puts(#x);
#define PI(A) cout<<(A)<<endl;
#define DG(x) cout<<#x<<“=”<<(x)<<endl;
#define DGG(x,y) cout<<#x<<“=”<<(x)<<” “<<#y<<“=”<<(y)<<endl;
#define DGGG(x,y,z) cout<<#x<<“=”<<(x)<<” “<<#y<<“=”<<(y)<<” “<<#z<<“=”<<(z)<<endl;
#define PIar(a,n) rep(i,n)cout<<a[i]<<” “;cout<<endl;
#define PIarr(a,n,m) rep(aa,n){rep(bb, m)cout<<a[aa][bb]<<” “;cout<<endl;}
const double EPS = 1e-9 ;
int T,n,q,c;
map<string,int> mp;
map<string,int>::iterator ite;
map<int,vector<string> > res;
string st;

inline int readt(int N){
    int ans=0,tit;
    rep(i,N){
        SI(tit);
        ans+=(1<<N-i-1) & (tit<<N-i-1);
    }
    return ans;
}

int main(){
    SI(T);
    while(T–){
        //测试数据可能出现重复的名字和情况,所以要初始化
        mp.clear();
        res.clear();
        SII(n,q);
        SI(c);
        rep(i,c){
            cin>>st;
            mp[st]=0;
        }
        rep(i,q){
            int nu;
            SI(nu);
            rep(j,nu){
                cin>>st;
                mp[st]+=(1<<q-i-1);
            }
        }
        for(ite=mp.begin();ite!=mp.end();ite++){
            res[ite->second].push_back(ite->first);
        }
        rep(i,n){
            int index=readt(q);
            if(res.find(index)==res.end()){
                puts(“Let’s go to the library!!”);
            }else{
                vector<string>& t=res[index];
                if(t.size()>1){
                    puts(“Let’s go to the library!!”);
                }else{
                    cout<<t[0]<<“\n”;
                }
            }
        }
    }
    return 0;
}

【D】

因为样例用的是m=3…所以我就一直卡在z>=3……然后比赛结束以后发现了…好亏啊

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
#define cle(a,val) memset(a,(val),sizeof(a))
#define SI(N) scanf(“%d”,&(N))
#define SII(N,M) scanf(“%d %d”,&(N),&(M))
#define SIII(N,M,K) scanf(“%d %d %d”,&(N),&(M),&(K))
#define rep(i,b) for(int i=0;i<(b);i++)
#define rez(i,a,b) for(int i=(a);i<=(b);i++)
#define red(i,a,b) for(int i=(a);i>=(b);i–)
const ll LINF = 0x3f3f3f3f3f3f3f3f;
#define PU(x) puts(#x);
#define PI(A) cout<<(A)<<endl;
#define DG(x) cout<<#x<<“=”<<(x)<<endl;
#define DGG(x,y) cout<<#x<<“=”<<(x)<<” “<<#y<<“=”<<(y)<<endl;
#define DGGG(x,y,z) cout<<#x<<“=”<<(x)<<” “<<#y<<“=”<<(y)<<” “<<#z<<“=”<<(z)<<endl;
#define PIar(a,n) rep(i,n)cout<<a[i]<<” “;cout<<endl;
#define PIarr(a,n,m) rep(aa,n){rep(bb, m)cout<<a[aa][bb]<<” “;cout<<endl;}
const double EPS = 1e-9 ;

struct Star{
    int left,right;
    bool operator<(const Star MM) const{
        return left<MM.left;
    }
}A[500],B[500];
int n,m,x,y,T,s,e;

int main(){
    SI(T);
    while(T–){
        SII(n,m);SII(x,y);
        rep(i,x){
            SII(s,e);
            A[i].left=s;
            A[i].right=e;
        }
        rep(i,y){
            SII(s,e);
            B[i].left=s;
            B[i].right=e;
        }
        sort(A,A+x);
        sort(B,B+y);
        int ans=0;
        rep(i,x){
            s=A[i].left;
            e=A[i].right;
            int z=0;
            rep(j,y){
                if(B[j].left>A[i].right) break;
                z+=(min(B[j].right,A[i].right)-max(A[i].left,B[j].left)+1);
                    if(z>=m){
                        ans+=z-m+1;
                        z=0;
                    }else{
                        z=0;
                    }
            }
        }
        printf(“%d\n”,ans);
    }
    return 0;
}

VJ SWPU-ACM省赛集训赛ONE J Right turn

【类型】

模拟

【Tip】

我的代码感觉上很对…然而莫名其妙总WA.然后把代码改成网上搜的题解的思路,A了…

我一开始的思路是floyd判圈法,若会碰到同一个路障第二次,则一定无法逃出去.

这个思路是错的,因为有可能在同一个点转的方向不同,所以如果经过同一个点两次有可能逃出去.

但每个点最多只能经过三次,第四次时一定是一个圈.所以判断是否经过一个点四次就好了.依然是floyd判圈法.不过要判四次.

然后成型代码如下.

【WA Code1】

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
#define cle(a,val) memset(a,(val),sizeof(a))
#define SI(N) scanf("%lld",&(N))
#define SII(N,M) scanf("%d %d",&(N),&(M))
#define SIII(N,M,K) scanf("%d %d %d",&(N),&(M),&(K))
#define rep(i,b) for(int i=0;i<(b);i++)
#define rez(i,a,b) for(int i=(a);i<=(b);i++)
#define red(i,a,b) for(int i=(a);i>=(b);i--)
const ll LINF = 0x3f3f3f3f3f3f3f3f;
#define PU(x) puts(#x);
#define PI(A) cout<<(A)<<endl;
#define DG(x) cout<<#x<<"="<<(x)<<endl;
#define DGG(x,y) cout<<#x<<"="<<(x)<<" "<<#y<<"="<<(y)<<endl;
#define DGGG(x,y,z) cout<<#x<<"="<<(x)<<" "<<#y<<"="<<(y)<<" "<<#z<<"="<<(z)<<endl;
#define PIar(a,n) rep(i,n)cout<<a[i]<<" ";cout<<endl;
#define PIarr(a,n,m) rep(aa,n){rep(bb, m)cout<<a[aa][bb]<<" ";cout<<endl;}
const double EPS = 1e-9 ;
pair<int,int> node;
map<pair<int,int>,bool> mp;
map<int,vector<int> > EdgeX,EdgeY;
int N,X,Y,step;
int toward[4]={1,-2,-1,2},t=0;//右下左上

bool floyd(){
    X=0,Y=0;
    while(1){
        if(toward[t]==1){
            vector<int>& Just=EdgeY[Y];
            int si=Just.size(),flag=0;
            rep(i,si){
                if(Just[i]>X){
                    if(mp[make_pair(Just[i],Y)]) return false;
                    t=(t+1)%4;
                    mp[make_pair(Just[i],Y)]=true;
                    flag=1;
                    X=Just[i]-1;
                    step++;
                    break;
                }
            }
            if(!flag) return true;
        }else if(toward[t]==-2){
            vector<int>& Just=EdgeX[X];
            int si=Just.size(),flag=0;
            red(i,si-1,0){
                if(Just[i]<Y){
                    if(mp[make_pair(X,Just[i])]) return false;
                    t=(t+1)%4;
                    mp[make_pair(X,Just[i])]=true;
                    Y=Just[i]+1;
                    step++;
                    flag=1;
                    break;
                }
            }
            if(!flag) return true;
        }else if(toward[t]==-1){
            vector<int>& Just=EdgeY[Y];
            int si=Just.size(),flag=0;
            red(i,si-1,0){
                if(Just[i]<X){
                    if(mp[make_pair(Just[i],Y)]) return false;
                    t=(t+1)%4;
                    mp[make_pair(Just[i],Y)]=true;
                    flag=1;
                    X=Just[i]+1;
                    step++;
                    break;
                }
            }
            if(!flag) return true;
        }else if(toward[t]==2){
            vector<int>& Just=EdgeX[X];
            int si=Just.size(),flag=0;
            rep(i,si){
                if(Just[i]>Y){
                    if(mp[make_pair(X,Just[i])]) return false;
                    t=(t+1)%4;
                    mp[make_pair(X,Just[i])]=true;
                    Y=Just[i]-1;
                    step++;
                    flag=1;
                    break;
                }
            }
            if(!flag) return true;
        }
    }
}

int main(){
    while(~SI(N)){
        t=0;
        step=0;
        mp.clear();
        EdgeX.clear();
        EdgeY.clear();
        rep(i,N){
            scanf("%d%d",&node.first,&node.second);
            mp[node]=false;
            EdgeX[node.first].push_back(node.second);
            EdgeY[node.second].push_back(node.first);
        }
        map<int,vector<int> >::iterator it;
        for(it=EdgeX.begin();it!=EdgeX.end();it++){
            vector<int>& Just=it->second;
            sort(Just.begin(),Just.end());
        }
        for(it=EdgeY.begin();it!=EdgeY.end();it++){
            vector<int>& Just=it->second;
            sort(Just.begin(),Just.end());
        }
        if(floyd()){
            printf("%d\n",step);
        }else{
            printf("-1\n");
        }
    }
    return 0;
}

【简单修改后AC代码】

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
#define cle(a,val) memset(a,(val),sizeof(a))
#define SI(N) scanf(“%lld”,&(N))
#define SII(N,M) scanf(“%d %d”,&(N),&(M))
#define SIII(N,M,K) scanf(“%d %d %d”,&(N),&(M),&(K))
#define rep(i,b) for(int i=0;i<(b);i++)
#define rez(i,a,b) for(int i=(a);i<=(b);i++)
#define red(i,a,b) for(int i=(a);i>=(b);i–)
const ll LINF = 0x3f3f3f3f3f3f3f3f;
#define PU(x) puts(#x);
#define PI(A) cout<<(A)<<endl;
#define DG(x) cout<<#x<<“=”<<(x)<<endl;
#define DGG(x,y) cout<<#x<<“=”<<(x)<<” “<<#y<<“=”<<(y)<<endl;
#define DGGG(x,y,z) cout<<#x<<“=”<<(x)<<” “<<#y<<“=”<<(y)<<” “<<#z<<“=”<<(z)<<endl;
#define PIar(a,n) rep(i,n)cout<<a[i]<<” “;cout<<endl;
#define PIarr(a,n,m) rep(aa,n){rep(bb, m)cout<<a[aa][bb]<<” “;cout<<endl;}
const double EPS = 1e-9 ;
pair<int,int> node;
map<pair<int,int>,int> mp;
map<int,vector<int> > EdgeX,EdgeY;
int N,X,Y,step;
int toward[4]={1,-2,-1,2},t=0;//右下左上

bool floyd(){
    X=0,Y=0;
    while(1){
        if(toward[t]==1){
            vector<int>& Just=EdgeY[Y];
            int si=Just.size(),flag=0;
            rep(i,si){
                if(Just[i]>X){
                    if(mp[make_pair(Just[i],Y)]==3) return false;
                    t=(t+1)%4;
                    mp[make_pair(Just[i],Y)]++;
                    flag=1;
                    X=Just[i]-1;
                    step++;
                    break;
                }
            }
            if(!flag) return true;
        }else if(toward[t]==-2){
            vector<int>& Just=EdgeX[X];
            int si=Just.size(),flag=0;
            red(i,si-1,0){
                if(Just[i]<Y){
                    if(mp[make_pair(X,Just[i])]==3) return false;
                    t=(t+1)%4;
                    mp[make_pair(X,Just[i])]++;
                    Y=Just[i]+1;
                    step++;
                    flag=1;
                    break;
                }
            }
            if(!flag) return true;
        }else if(toward[t]==-1){
            vector<int>& Just=EdgeY[Y];
            int si=Just.size(),flag=0;
            red(i,si-1,0){
                if(Just[i]<X){
                    if(mp[make_pair(Just[i],Y)]==3) return false;
                    t=(t+1)%4;
                    mp[make_pair(Just[i],Y)]++;
                    flag=1;
                    X=Just[i]+1;
                    step++;
                    break;
                }
            }
            if(!flag) return true;
        }else if(toward[t]==2){
            vector<int>& Just=EdgeX[X];
            int si=Just.size(),flag=0;
            rep(i,si){
                if(Just[i]>Y){
                    if(mp[make_pair(X,Just[i])]==3) return false;
                    t=(t+1)%4;
                    mp[make_pair(X,Just[i])]++;
                    Y=Just[i]-1;
                    step++;
                    flag=1;
                    break;
                }
            }
            if(!flag) return true;
        }
    }
}

int main(){
    while(~SI(N)){
        t=0;
        step=0;
        mp.clear();
        EdgeX.clear();
        EdgeY.clear();
        rep(i,N){
            scanf(“%d%d”,&node.first,&node.second);
            mp[node]=0;
            EdgeX[node.first].push_back(node.second);
            EdgeY[node.second].push_back(node.first);
        }
        map<int,vector<int> >::iterator it;
        for(it=EdgeX.begin();it!=EdgeX.end();it++){
            vector<int>& Just=it->second;
            sort(Just.begin(),Just.end());
        }
        for(it=EdgeY.begin();it!=EdgeY.end();it++){
            vector<int>& Just=it->second;
            sort(Just.begin(),Just.end());
        }
        if(floyd()){
            printf(“%d\n”,step);
        }else{
            printf(“-1\n”);
        }
    }
    return 0;
}

【跟着题解AC Code】

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
#define cle(a,val) memset(a,(val),sizeof(a))
#define SI(N) scanf(“%lld”,&(N))
#define SII(N,M) scanf(“%d %d”,&(N),&(M))
#define SIII(N,M,K) scanf(“%d %d %d”,&(N),&(M),&(K))
#define rep(i,b) for(int i=0;i<(b);i++)
#define rez(i,a,b) for(int i=(a);i<=(b);i++)
#define red(i,a,b) for(int i=(a);i>=(b);i–)
const ll LINF = 0x3f3f3f3f3f3f3f3f;
#define PU(x) puts(#x);
#define PI(A) cout<<(A)<<endl;
#define DG(x) cout<<#x<<“=”<<(x)<<endl;
#define DGG(x,y) cout<<#x<<“=”<<(x)<<” “<<#y<<“=”<<(y)<<endl;
#define DGGG(x,y,z) cout<<#x<<“=”<<(x)<<” “<<#y<<“=”<<(y)<<” “<<#z<<“=”<<(z)<<endl;
#define PIar(a,n) rep(i,n)cout<<a[i]<<” “;cout<<endl;
#define PIarr(a,n,m) rep(aa,n){rep(bb, m)cout<<a[aa][bb]<<” “;cout<<endl;}
const double EPS = 1e-9 ;
pair<int,int> node;
map<pair<int,int>,bool> mp;
map<int,vector<int> > EdgeX,EdgeY;
int N,X,Y,step;
int toward[4]={1,-2,-1,2},t=0;//右下左上

bool floyd(){
    X=0,Y=0;
    while(step<=4*N+1){
        int tmpx=-INF,tmpy=-INF;
        if(toward[t]==1){
            vector<int>& Just=EdgeY[Y];
            int si=Just.size();
            rep(i,si){
                if(Just[i]>X){
                    tmpy=Y;
                    if(tmpx!=-INF) tmpx=min(tmpx,Just[i]);
                    else tmpx=Just[i];
                }
            }
            if (tmpx == -INF || tmpy == -INF) return true;
            else{
    //            if(mp[make_pair(tmpx,Y)]) return false;
     //           mp[make_pair(tmpx,Y)]=true;
                X=tmpx-1;
                step++;
                t=(t+1)%4;
            }

        }else if(toward[t]==-2){
            vector<int>& Just=EdgeX[X];
            int si=Just.size(),flag=0;
            rep(i,si){
                if(Just[i]<Y){
                    tmpx=X;
                    flag=1;
                    if(tmpy!=-INF) tmpy=max(tmpy,Just[i]);
                    else tmpy=Just[i];
                }
            }
            if (tmpx == -INF || tmpy == -INF) return true;
            else{
  //              if(mp[make_pair(X,tmpy)]) return false;
 //               mp[make_pair(X,tmpy)]=true;
                Y=tmpy+1;
                step++;
                t=(t+1)%4;
            }
        }else if(toward[t]==-1){
            vector<int>& Just=EdgeY[Y];
            int si=Just.size(),flag=0;
            rep(i,si){
                if(Just[i]<X){
                    flag=1;
                    tmpy=Y;
                    if(tmpx!=-INF) tmpx=max(tmpx,Just[i]);
                    else tmpx=Just[i];
                }
            }
            if (tmpx == -INF || tmpy == -INF) return true;
            else{
 //               if(mp[make_pair(tmpx,Y)]) return false;
 //               mp[make_pair(tmpx,Y)]=true;
                X=tmpx+1;
                step++;
                t=(t+1)%4;
            }
        }else if(toward[t]==2){
            vector<int>& Just=EdgeX[X];
            int si=Just.size(),flag=0;
            rep(i,si){
                if(Just[i]>Y){
                    tmpx=X;
                    flag=1;
                    if(tmpy!=-INF) tmpy=min(tmpy,Just[i]);
                    else tmpy=Just[i];
                }
            }
            if (tmpx == -INF || tmpy == -INF) return true;
            else{
 //              if(mp[make_pair(X,tmpy)]) return false;
  //              mp[make_pair(X,tmpy)]=true;
                Y=tmpy-1;
                step++;
                t=(t+1)%4;
            }
        }
    }
    return false;
}

int main(){
    while(~SI(N)){
        t=0;
        step=0;
        mp.clear();
        EdgeX.clear();
        EdgeY.clear();
        rep(i,N){
            scanf(“%d%d”,&node.first,&node.second);
//            mp[node]=false;
            EdgeX[node.first].push_back(node.second);
            EdgeY[node.second].push_back(node.first);
        }
        if(floyd()){
            printf(“%d\n”,step);
        }else{
            printf(“-1\n”);
        }
    }
    return 0;
}

第七届山东省ACM/ICPC H Memory Leak

【类型】

模拟,感受一下什么叫绝望吧…

【Tip】

F**k!…..QNMD鲁棒性….QAQ

后记…发现自己的代码可以过…但是忘了关freopean..所以才WA…尴尬//= // =//

【Code】

鲁棒形比我好,一点的,代码.

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
int T;
char name[10010],stri[10010];
int num;
struct Star{
    char s[2000];
    char contain[10010];
    int ind;
    bool has_end;
};
Star S[10010];
int main(){
 //   #ifndef DEF
 //    freopen(“in.txt”,”r”,stdin);
 //    freopen(“out.txt”,”w”,stdout);
 //  #endif // DEF
    scanf(“%d”,&T);
        while(T–){
            char op[100],def[10100];
            num=0;
            while(scanf(“%s”,op)){
                if(op[3]==’u’){
                    scanf(“%*s”);
                    break;
                }
                if(op[3]==’r’){
                    while(scanf(“%s”,def)){
                        int flag=1,star_num=0,ind_num=0,len=strlen(def);
                        for(int i=0;i<len;++i){
                            if(flag==1 && def[i]!='[‘){
                                S[num].s[star_num++]=def[i];
                            }
                            if(def[i]=='[‘){
                                S[num].s[star_num]=0;
                                flag=2;
                                continue;
                            }
                            if(flag==2 && def[i]!=’]’){
                                ind_num=ind_num*10+(def[i]-‘0’);
                            }
                            if(def[i]==’]’){
                                S[num].contain[0]=0;//初始化
                                S[num].has_end=true;
                                S[num].ind=ind_num;
                                star_num=0;
                                ind_num=0;
                                num++;
                                continue;
                            }
                        }
                        if(def[len-1]==’;’) break;
                    }
                }
                if(op[3]==’s’){
                    scanf(“%s%*c”,name);
                    gets(stri);
                    int index=num;
                    for(int i=0;i<num;++i){
                        if(!strcmp(S[i].s,name))
                            index=i;
                    }
                    int len=strlen(stri);
                    if(len>=S[index].ind){
                        S[index].has_end=false;
                        stri[S[index].ind]=0;//’\0′
                    }else S[index].has_end=true;
                    strcpy(S[index].contain,stri);
                }
                if(op[3]==’t’){
                    scanf(“%s”,name);
                    int index=num;
                    for(int i=0;i<num;++i){
                        if(!strcmp(S[i].s,name))
                            index=i;
                    }
                    for(int i=index;i<num;++i){
                        printf(“%s”,S[i].contain);
                        if(S[i].has_end) break;
                    }
                    printf(“\n”);
                }
            }
        }
    return 0;
}

我的代码

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
int T;
char name[10010],stri[10010];
int num=0;
struct Star{
    char s[2000];
    char contain[10010];
    int ind;
    bool has_end;
};
Star S[10010];
int main(){
//   #ifndef DEF  //<-F**k U
  //   freopen(“in.txt”,”r”,stdin);
  //   freopen(“out.txt”,”w”,stdout);
 //  #endif // DEF
    scanf(“%d”,&T);
        while(T–){
            char op[10],def[10100];
            num=0;
            while(scanf(“%s”,op)){
                scanf(” “);
                if(op[3]==’u’){
                    scanf(“%*s”);
                    break;
                }
                if(op[3]==’r’){
                    int flag=1,star_num=0,ind_num=0;
                    gets(def);
                    for(int i=0,start=0;def[i]!=’\0′;++i){
                        if(def[i]==’ ‘ || def[i]==’,’) continue;
                        if(flag==1 && def[i]!='[‘){
                            S[num].s[star_num++]=def[i];
                        }else if(def[i]=='[‘){
                            S[num].s[star_num]=0;
                            flag=2;
                        }else if(flag==2 && def[i]!=’]’){
                            ind_num=ind_num*10+(def[i]-‘0’);
                        }else if(def[i]==’]’){
                            S[num].contain[0]=0;//初始化
                            S[num].has_end=true;
                            S[num].ind=ind_num;
                            star_num=0;
                            ind_num=0;
                            num++;
                            flag=1;
                        }else if(def[i]==’;’)
                            break;
                    }
                }
                if(op[3]==’s’){
                    scanf(“%s%*c”,name);
                    gets(stri);
                    int index;
                    for(int i=0;i<num;++i){
                        if(!strcmp(S[i].s,name))
                            index=i;
                    }
                    int len=strlen(stri);
                    if(len>=S[index].ind){
                        S[index].has_end=false;
                        stri[S[index].ind]=0;//’\0′
                    }else S[index].has_end=true;
                    strcpy(S[index].contain,stri);
                }
                if(op[3]==’t’){
                    scanf(” “);
                    gets(name);
                    int index;
                    for(int i=0;i<num;++i){
                        if(!strcmp(S[i].s,name))
                            index=i;
                    }
                    for(int i=index;i<num;++i){
                        printf(“%s”,S[i].contain);
                        if(S[i].has_end) break;
                    }
                    printf(“\n”);
                }
            }
        }
    return 0;
}

LA 2995

【生词】

small lightweight object 轻量级的对象(比较轻的物体)

hold 控制,保留,支持,持有,保存,这里意为举起

intelligence 智力,情报工作,情报机关,理解力

determine 下决心,决定

cardinal 主要的,基本的

inferring 推理,猜想

upper limited 上限,最大值

assume 借取,篡夺,假定,假想

form 形式,形状,构成

lattice 晶格,格子,格架

cubes 立方体

weighs权衡,重量为

gram 克/g

is not necessarily 没必要/不一定

separated 分隔,分开的

corresponds 符合,一致,相应

similar 类似的,相似的

【Tip】

这个模拟…额…有点蒙..效率起见,回头看,蓝书P15

【Code】

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define REP(i,n) for(int i=0;i<(n);++i)
using namespace std;
const int maxn =10;
int n;
char pos[maxn][maxn][maxn];
char view[6][maxn][maxn];

char read_char(){
    char ch;
    for(;;){
        ch=getchar();
        if((ch>=’A’ && ch<=’Z’) || ch==’.’) return ch;
    }
}

//get函数表示第k个视图中,第i行j列,深度为len的单位立方体
//在原立方体中的坐标(x,y,z)
void get(int k,int i,int j,int len,int &x,int &y,int &z){
    if(k==0){x=len;y=j;z=i;}
    if(k==1){x=n-1-j;y=len;z=i;}
    if(k==2){x=n-1-len;y=n-1-j;z=i;}
    if(k==3){x=j;y=n-1-len;z=i;}
    if(k==4){x=n-1-i;y=j;z=len;}
    if(k==5){x=i;y=j;z=n-1-len;}
}
int main(){
    while(~scanf(“%d”,&n) && n){
        REP(i,n) REP(k,6) REP(j,n) view[k][i][j]=read_char();
        REP(i,n) REP(j,n) REP(k,n) pos[i][j][k]=’#’;

        REP(k,6) REP(i,n) REP(j,n) if(view[k][i][j]==’.’)
            REP(p,n){
                int x,y,z;
                get(k,i,j,p,x,y,z);
                pos[x][y][z]=’.’;
            }

        for(;;){
            bool done=true;
            REP(k,6) REP(i,n) REP(j,n) if(view[k][i][j]!=’.’){
                REP(p,n){
                    int x,y,z;
                    get(k,i,j,p,x,y,z);
                    if(pos[x][y][z]==’.’) continue;
                    if(pos[x][y][z]==’#’) {
                        pos[x][y][z]=view[k][i][j];
                        break;
                    }
                    if(pos[x][y][z]==view[k][i][j]) break;
                    pos[x][y][z]=’.’;
                    done=false;
                }
            }
            if(done) break;
        }

        int ans=0;
        REP(i,n) REP(j,n) REP(k,n)
            if(pos[i][j][k]!=’.’) ans++;

        printf(“Maximum weight: %d gram(s)\n”,ans);
    }
    return 0;
}