CUIT MAGICIAN UNION 2017 TRAINING #2

第一题 Grid

#include <cstdio>
#include <cstring>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <deque>
#include <cstdlib>
#define eps 1e-6
#define ll long long
#define MAXN 10100
#define INF 0x3fffffff
#define mod 1000000007
#define clr(x) memset(x,0,sizeof(x))
#define de1 printf("!\n")
#define de2 printf("!!\n")
#define de3 printf("!!!\n")
#define pn printf("\n")
#define biaoji printf("\\!!/")
using namespace std;

int n,m,res;
char mm[555][555];
int maze[555][555];
int dx[4]={1,-1,0,0};
int dy[4]={0,0,-1,1};
int vis[555][555];
int step;

struct node
{
    int x,y;
    int step;
};

void bfs()
{
    node a;
    a.x = 0;
    a.y = 0;
    a.step = 0;
    queue<node>Q;
    Q.push(a);
    vis[0][0] = 1;

    while(!Q.empty())
    {
        node tem = Q.front();
        Q.pop();

        if(tem.x == m-1 && tem.y == n-1)
        {
            printf("%d\n",tem.step);
            return ;
        }
        else
        {
            for(int i=0;i<4;i++)
            {
                node tt;
                tt.x = tem.x + dx[i] * maze[tem.x][tem.y];
                tt.y = tem.y + dy[i] * maze[tem.x][tem.y];
                if(tt.x>=0 && tt.x< m && tt.y >= 0 && tt.y <n && !vis[tt.x][tt.y])
                {
                    tt.step = tem.step + 1;
                    vis[tt.x][tt.y] = 1;
                    Q.push(tt);
                }
            }
        }
    }
    printf("-1\n");
    return ;
}


int main()
{
    while(cin>>m>>n)
    {
        clr(maze);
        clr(vis);
        for(int i=0;i<m;i++)
        {
            scanf("%s",mm[i]);
        }

        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                maze[i][j] = mm[i][j] - '0';
            }
        }

        bfs();
    }
    return 0;
}

第二题 Summer Trip

#include <cstdio>
#include <cstring>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <deque>
#include <cstdlib>
#define eps 1e-6
#define ll long long
#define MAXN 10100
#define INF 0x3fffffff
#define mod 1000000007
#define clr(x) memset(x,0,sizeof(x))
#define de1 printf("!\n")
#define de2 printf("!!\n")
#define de3 printf("!!!\n")
#define pn printf("\n")
#define biaoji printf("\\!!/")
using namespace std;

int pre[1010];
int num[1010];
int vis[1010];
int tt[1010];


bool cmp(int a,int b)
{
    return vis[a]<vis[b];
}

int Find(int x)
{
    if(pre[x] == x) return x;
    return pre[x] = Find(pre[x]);
}

void Union(int a,int b)
{
    int A = Find(a);
    int B = Find(b);
    if(A!=B)
    {
        pre[B] = A;
    }
}


int main()
{
    int t,u,v,n,m,cas = 1;
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        clr(num);
        clr(vis);
        clr(tt);
        for(int i=1;i<=n;i++)
        {
            pre[i] = i;
        }
        for(int i=1;i<=n;i++)
        {
            cin>>num[i];
        }
        for(int j=1;j<=m;j++)
        {
            cin>>u>>v;
            Union(u,v);
        }
        int pos = 0;
        for(int i=1;i<=n;i++)
        {
            int xx = Find(i);
            if(!vis[xx]) tt[pos++]=xx;
            vis[xx]+=num[i];
        }
        sort(tt,tt+pos,cmp);
        printf("Case %d: %d\n",cas++,pos);
        for(int i=0;i<pos;i++)
        {
            if( i != pos - 1 ) printf("%d ",vis[tt[i]]);
            else printf("%d\n",vis[tt[i]]);
        }
    }
    return 0;
}

第三题 Matrices with XOR property

#include <cstdio>
#include <cstring>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <deque>
#include <cstdlib>
#define eps 1e-6
#define ll long long
#define MAXN 10100
#define INF 0x3fffffff
#define mod 1000000007
#define clr(x) memset(x,0,sizeof(x))
#define de1 printf("!\n")
#define de2 printf("!!\n")
#define de3 printf("!!!\n")
#define pn printf("\n")
#define biaoji printf("\\!!/")
using namespace std;

int vis[100010];
int maze[1010][1010];
int main()
{
    int t , n , m ;
    scanf("%d",&t);
    while ( t-- )
    {
        int pos=0;
        scanf("%d%d",&n,&m);
        clr(vis);
        for(int i = 1; i <= n; i++)
        {
            for ( int j = 1 ; j <= m ; j++)
            {
                maze[i][j] = i^j;
                pos = max(pos,maze[i][j]);
                vis[maze[i][j]]++;
            }
        }
        ll ans = 1;
        for(int i=0;i<=pos;i++){
            if(vis[i] == 0) continue;
            ll pro = 1;
            for(int j=vis[i];j>=1;j--)
            {
                pro=(pro*j)%mod;
            }
            ans=(ans*pro)%mod;
        }
        printf("%lld\n",ans);
    }

    return 0;
}

第四题 Weird Rounding

#include <cstdio>
#include <cstring>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <deque>
#include <cstdlib>
#define eps 1e-6
#define ll long long
#define MAXN 10100
#define INF 0x3fffffff
#define mod 1000000007
#define clr(x) memset(x,0,sizeof(x))
#define de1 printf("!\n")
#define de2 printf("!!\n")
#define de3 printf("!!!\n")
#define pn printf("\n")
#define biaoji printf("\\!!/")
using namespace std;

int num[100];

int main()
{
    ll n,k,pos=0;;
    cin>>n>>k;
    if(n == 0) {printf("0\n");return 0;}

    int yy = n;
    while(yy)
    {
        num[pos++]=yy%10;
        yy/=10;
    }

    ll xx = 1;
    for ( int i = 0 ; i < k ; i++ ){
        xx *= 10;
    }

    if( xx > n )
    {
        printf("%d\n",pos-1);return 0;
    }
    else
    {
        int res=0;
        int cnt=0;
        for ( int i = 0 ; i < pos ; i++ )
        {
            if ( cnt == k ){ break; }
            if ( num[i] ){ res++; }
            if ( !num[i] ){ cnt++; }
        }
        if(cnt < k) printf("%d\n",pos-1);
        else printf("%d\n",res);
    }
    return 0;
}

第五题 Dishonest Sellers

#include <cstdio>
#include <cstring>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <deque>
#include <cstdlib>
#define eps 1e-6
#define ll long long
#define MAXN 10100
#define INF 0x3fffffff
#define mod 1000000007
#define clr(x) memset(x,0,sizeof(x))
#define de1 printf("!\n")
#define de2 printf("!!\n")
#define de3 printf("!!!\n")
#define pn printf("\n")
#define biaoji printf("\\!!/")
using namespace std;

ll A[201010];
ll B[201010];
struct node
{
    int val;
    int id;
}ca[201010];
int vis[201010];


bool cmp(node a,node b)
{
    return a.val < b.val;
}

int main()
{
    int n , k ;
    scanf("%d%d" , &n , &k);
     memset(vis,0,sizeof(vis));
    for ( int i = 0 ; i < n ; i++){
        scanf ( "%I64d" , &A[i] );
    }
    for ( int j = 0 ; j < n ; j++){
        scanf ( "%I64d" , &B[j] );
    }

    for ( int k = 0 ; k < n ; k++){
        ca[k].val = A[k] - B[k];
        ca[k].id = k;
    }

    sort(ca, ca + n , cmp);

    /*for(int i = 1 ; i <= n ; i++)
    {
        cout <<"ca["<< i <<"]  val : "<< ca[i].val <<" id : "<<ca[i].id<<endl;
        cout << A[ca[i].id] << " " << B[ca[i].id] <<endl;
    }*/
    ll sum = 0;
    for(int i = 0 ; i < n ; i++)
    {
        if(i > k - 1 && ca[i].val > 0) { break; }
        sum += A[ca[i].id];
        vis[ca[i].id]=1;
    }
    for(int j = 0 ; j < n ; j++)
    {
        if(!vis[ca[j].id])
            sum += B[ca[j].id];
    }
    printf("%I64d\n",sum);
    return 0;
}
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 202,980评论 5赞 476
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 85,178评论 2赞 380
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 149,868评论 0赞 336
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 54,498评论 1赞 273
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 63,492评论 5赞 364
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,521评论 1赞 281
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 37,910评论 3赞 395
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,569评论 0赞 256
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 40,793评论 1赞 296
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,559评论 2赞 319
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,639评论 1赞 329
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,342评论 4赞 318
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 38,931评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,904评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,144评论 1赞 259
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 42,833评论 2赞 349
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,350评论 2赞 342

推荐阅读更多精彩内容