比赛链接:http://acm.csu.edu.cn/OnlineJudge/contest.php?cid=2024

A、逆元
题目要求:给定正整数x,y,求最小的正整数z使得x*z mod y = 1。
输入:x,y(2<=x,y<10^6)
输出:z或No

解题思路:因为y值不是很大,所以我就用暴力求解,一个for循环解决

#include <stdio.h>

#define intt long long

void solve(intt x,intt y){
    intt i;
    if(x%y==0){
        printf(“No\n”);
        return ;
    }
    for(i=1;i<y;i++){
        if((x*i)%y==1)
            break;
    }
    if(i==y)
        printf(“No\n”);
    else
        printf(“%lld\n”,i);
}
int main(){
    intt x,y;
    while(scanf(“%lld%lld”,&x,&y)!=EOF){
        solve(x,y);
    }
    return 0;
}

B、处理RankList
题目要求:把每个题目的提交次数和时间合在一起
输入:多组测试数据。每组两行字符串。格式如下
SJTU_TeamC[TAB]4:31:41[TAB]0:41:17[TAB]3:06:46[TAB]4:05:51[TAB]1:01:51
[TAB](-1)[TAB][TAB](-1)[TAB](-4)[TAB](-1)
输出:格式如下
SJTU_TeamC[TAB]4:31:41(-1)[TAB]0:41:17[TAB]3:06:46(-1)[TAB]4:05:51(-4)[TAB]1:01:51(-1)
解题思路:请允许我用N分钟来咒骂一下。这是啥破题,纠结死我了…= =…

收获:原来’\t’不等于8个空格,他就是一个字符。这个道理咱都懂,可是做起来怎么就…

———–华丽丽的分割线——-引用下李新强小朋友的代码,不过我稍微改了下哈~~————

#include<iostream>
#include<cstring>
using namespace std;

int main(){
    char str[20][50];
    char name[50];
    char times[20][50];
    char s[500];
    while(gets(s)){
        int k=0,i,j,p=0;
        for(i=0;s[i];i++){
            if(s[i]==’\t’)
                break;
            name[k++]=s[i];
        }
        name[k]=0;
        k=0;
        p=0;
        for(j=i+1;s[j];j++){
            if(s[j]==’\t’){
                str[k][p]=0;
                k++;
                p=0;
                continue;
            }
            else
                str[k][p++]=s[j];
        }
        str[k][p]=0;
        gets(s);
        int flag=0;
        k=0;
        p=0;
        for(i=1;s[i];i++){
            if(s[i-1]==’\t’&&s[i]==’\t’){
                times[k++][p]=0;
                continue;
            }
            if(s[i]==’\t’&&flag){
                times[k][p]=0;
                k++;
                p=0;
                flag=0;
                continue;
            }
            else{
                flag=1;
                times[k][p++]=s[i];
            }
        }
        times[k][p]=0;
        cout<<name;
        for(i=0;i<5;i++)
            cout<<‘\t'<<str[i]<<times[i];
        cout<<endl;
    }
    return 0;

C、开机
题目大意:机房有很多机器,不同机器开机时间不同。已知开始站在1号机器,从一台机器走到另一台机器需要5秒,如何才能用最短的时间打开所有的机器。
输入:每组数据开头一个n表示机器数,接下来n个数表示1~n号机器所需开机时间,以秒为单位。0 < n <= 1000,开机时间为10~60秒。
输出:每组数据输出一行一个数,表示所有机器打开所需最短时间。
解题思路:将除了第一台机器以外(因为第一台不需要花时间过去)的所有机器的开机时间成降序排序,每往后走一台,时间加5秒,求时间最大值即可。

#include <stdio.h>
#include <stdlib.h>

#define N 1005

int a[N];

int cmp(const void *a,const void *b){
    return *(int *)b-*(int *)a;
}

int main(){
    int n;
    while(scanf(“%d”,&n)!=EOF){
        int i,min=0;
        for(i=0;i<n;i++)
            scanf(“%d”,&a[i]);
        min=a[0];
        qsort(a+1,n-1,sizeof(int),cmp);
        for(i=1;i<n;i++){
            if(a[i]+i*5>min)
                min=a[i]+i*5;
        }
        printf(“%d\n”,min);
    }
    return 0;
}

G、维护序列
题目大意:现在有一个N个整数组成的序列,这N个整数的标号分别为1, 2, …, N,对这个序列一共进行两类操作:
① 1 x y:表示将第x个和第y个(包括x、y)整数之间的所有整数的二进制的最低位的1变为0,如果某个整数的值为0,则不对这个整数做任何改变。
② 2 x y :表示你需要回答第x个和第y个(包括x、y)整数之间的所有整数异或的结果。
输入:对于每组测试数据,第一行包含两个正整数N(2<=N<=10^4)、M(1<=M<=10^5),表示这个序列一共有N个不超过2^30的整数,你需要处理M次操作。接下来一共有M行,每行均描述了一种操作。
输出:对于每个第②类操作,用一行输出一个整数表示回答的结果。
解题思路:挨个求解,TLE无疑。所以用线段树。特别处理全零区间,对于全零区间,不需要更新

收获:将一个整数x的二进制的最低位的1变为0的方法:x^=(-x&x),太华丽丽了

#include <stdio.h>

struct f{
    int l,r;
    int sum;
    int zero;
}node[50005];

//线段数的建立
void bulid(int k,int ll,int rr){
    node[k].l=ll;
    node[k].r=rr;
    if(ll==rr){
        scanf(“%d”,&node[k].sum);
        node[k].zero=node[k].sum;
        return ;
    }
    bulid(2*k,ll,(ll+rr)/2);
    bulid(2*k+1,(ll+rr)/2+1,rr);
    node[k].sum=node[2*k].sum^node[2*k+1].sum;
    node[k].zero=node[2*k].zero|node[2*k+1].zero;
}

void update(int k,int ll,int rr){
    int mid=(node[k].l+node[k].r)/2;
    if(node[k].zero==0)                 //全零区间
        return ;
    if(node[k].l==node[k].r){
        node[k].sum^=(node[k].sum&(-node[k].sum));
        node[k].zero=node[k].sum;
        return ;
    }
    if(ll<=mid)                                        //左
        update(2*k,ll,rr);
    if(rr>=mid+1)                                  //右
        update(2*k+1,ll,rr);
    node[k].sum=node[2*k].sum^node[2*k+1].sum;
    node[k].zero=node[2*k].zero|node[2*k+1].zero;
}

void print(int k,int ll,int rr,int *ans){
    int mid=(node[k].l+node[k].r)/2;
    if(node[k].l>=ll && node[k].r<=rr){         //找到区间
        *ans^=node[k].sum;
        return ;
    }
    if(ll<=mid)
        print(2*k,ll,rr,ans);
    if(rr>=mid+1)
        print(2*k+1,ll,rr,ans);
}

void solve(int flag,int ll,int rr){
    int ans=0;
    if(flag==1)
        update(1,ll,rr);
    else{
        print(1,ll,rr,&ans);
        printf(“%d\n”,ans);
    }
}

int main(){
    int n,m;
    while(scanf(“%d%d”,&n,&m)!=EOF){
        int i,x,y,flag;
        bulid(1,1,n);
        for(i=0;i<m;i++){
            scanf(“%d%d%d”,&flag,&x,&y);
            if(x>y){x^=y;y^=x;x^=y;}
            solve(flag,x,y);
        }
    }
    return 0;
}

H、跳跳
题目大意:一个每块地板标记着0~9某个数字的迷宫,其中标记1的地板不可以走,标记2~9的地板可以不花时间地跳到任意相同数字的位置,也可以和标记0的地板一样向前后左右任意方向花1个单位时间移动1的距离。给出起点和终点,求起点到终点的最短时间。
输入:每组数据第一行一个n,表示尺寸,2 <= n <= 100。接下来n行每行n个0~9的字符,或S表示起点,E表示终点,S和E的运动规则与0相同。整个地图只有一个S和一个E。
输出:每组数据输出一个数,占一行,表示起点到终点可以花费的最短时间。如果无法到达重点,输出”Oh No!”
解题思路:广搜。将相同的标记“2~9”,一个入队,全部入队,因为不花时间即可到达。

———–华丽丽的分割线——-我怎么在一个主函数里写勒,不是我风格哈,凑合看,不改了哈~~————

#include <stdio.h>
#include <queue>
using namespace std;

#define N 120

queue<int>Q;
char a[N][N],vis[N][N];
int dis[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
struct f{
    int pos[N*N];
    int len;
}dd[10];

int main(){
    int n;
    while(scanf(“%d”,&n)!=EOF){
        int i,j,x,y,b,cnt,end;
        getchar();
        while(!Q.empty())
            Q.pop();
        memset(dd,0,sizeof(dd));
        for(i=0;i<n;i++){
            for(j=0;j<n;j++){
                scanf(“%c”,&a[i][j]);
                vis[i][j]=0;
                if(a[i][j]==’S’){
                    Q.push(i*n+j);
                    Q.push(0);
                    vis[i][j]=1;
                }
                else if(a[i][j]==’E’)
                    end=i*n+j;
                else if(a[i][j]>=’2′ && a[i][j]<=’9′)
                    dd[a[i][j]-‘0’].pos[dd[a[i][j]-‘0’].len++]=i*n+j;
            }
            getchar();
        }
        while(!Q.empty()){
            b=Q.front();
            Q.pop();
            cnt=Q.front();
            Q.pop();
            if(b==end)
                break;
            for(i=0;i<4;i++){                
                x=b/n+dis[i][0];
                y=b%n+dis[i][1];
                if(x>=0 && x<n && y>=0 && y<n && a[x][y]!=’1′ && !vis[x][y]){
                    if(a[x][y]>=’2′ && a[x][y]<=’9′){
                        int k=a[x][y]-‘0’;
                        for(j=0;j<dd[k].len;j++){
                            Q.push(dd[k].pos[j]);
                            Q.push(cnt+1);
                            vis[dd[k].pos[j]/n][dd[k].pos[j]%n]=1;
                        }
                    }
                    else{
                        Q.push(x*n+y);
                        Q.push(cnt+1);
                        vis[x][y]=1;
                    }
                }
            }
        }

        if(Q.empty())
            printf(“Oh No!\n”);
        else
            printf(“%d\n”,cnt);
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。

Post Navigation