2019年全国高校计算机能力挑战赛 C语言程序设计决赛

毕竟这个比赛是第一次举办，能理解。。
希望未来再举办时，能够再完善一下题面表述、数据范围。

话说区域赛获奖名额有点少吧。舍友花60块想混个创新创业分也太难。。

水进了决赛圈，一共6题。
前4题，大概C语言课后习题的难度？
第5题，贪心排个序就好了吧
第6题，图论，拓扑排序，但我用暴力的，因为不知道范围呀，希望能骗点分。

第1题

#include<stdio.h>

const int maxn = 10050;
char s[maxn];
int cnt[5];

int main(){
    char c;
    int pos = 0;
    while((c = getchar()) != EOF){
        s[pos++] = c;
    }
    for(int i=0;i<pos;i++){
        if(s[i] == '+') cnt[1]++;
        else if(s[i] == '-') cnt[2]++;
        else if(s[i] == '*') cnt[3]++;
        else if(s[i] == '/') cnt[4]++;
    }
    printf("+ %d\n",cnt[1]);
    printf("- %d\n",cnt[2]);
    printf("* %d\n",cnt[3]);
    printf("/ %d\n",cnt[4]);
    return 0;
}

第2题

#include<stdio.h>

const int maxn = 450;
int n;
int a[maxn][maxn];

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            scanf("%d",&a[i][j]);
        }
    }
    int cnt = 0;
    for(int i=1;i<=n;i++){
        if(a[i][i] > 0) 
            cnt++;
    }
    for(int i=1;i<=n;i++){
        int pos = n-i+1;
        if(pos == i) continue;
        else{
            if(a[i][pos] > 0) 
                cnt++;
        }
    }
    printf("%d",cnt);
    return 0;
}
/*
4
1 2 3 4
5 6 7 8
9 0 0 12
1 0 0 -16
*/

第3题

#include<stdio.h>

typedef long long ll;
const int maxn = 1010;
int n;
ll a[maxn];
ll b[maxn];

int main(){
    scanf("%d",&n);
    bool flag = true;
    for(int i=1;i<=n;i++){
        scanf("%ld",&a[i]);
        int temp = a[i];
        int min_x = 9;
        while(temp){
            if(temp%10 < min_x) min_x = temp%10;
            temp /= 10;
        }
        ll new_num;
        if(a[i] == 0){
            new_num = a[i];
            b[i] = new_num;
            flag = false;
        }else{
            ll new_num = (a[i]/100*10+min_x)*10+min_x;
            b[i] = new_num;
            if(b[i] == a[i]) flag = false;
        }
    }
    if(flag == true){
        printf("Done");
        for(int i=1;i<=n;i++) printf(" %ld",b[i]);
    }else{
        printf("Error");
        for(int i=1;i<=n;i++) {
            if(b[i] == a[i]) printf(" %ld",b[i]);
        }
    }
    return 0;
}

/*
4
321 96 5 232
3
0 9 322
*/

第4题

#include<stdio.h>

const int maxn = 10010;
char s[maxn];
char ans[maxn];
int pos = 0;

void solve(int start,int ends){
    for(int i=start;i<ends;i++){
        for(int j=start+1;j<ends;j++){
            if((s[i] >= 'A' && s[i] <= 'Z') || (s[i] >= 'a' && s[i] <= 'z')){
                if((s[j] >= 'A' && s[j] <= 'Z') || (s[j] >= 'a' && s[j] <= 'z')){
                    if(s[i] == (s[j] + 1) || s[i] == (s[j] - 1)){
                        ans[pos++] = ' ';
                        for(int j=start;j<ends;j++){
                            ans[pos++] = s[j];
                        }
                        return;
                    }
                }
            }
        }
    }
}

int main(){
//  freopen("out.txt","w",stdout);
    char c;
    int start = 0;
    int ends = 0;
    while((c = getchar()) != EOF){
        s[ends++] = c;
        if(c == '.'){ //处理最后一个 
            solve(start,ends-1);
            break;
        }
        if(c == ' '){
            solve(start,ends-1);
            start = ends;
        }
    }
    if(pos == 0) printf("Accept!");
    else{
        for(int i=1;i<pos;i++) printf("%c",ans[i]);
    }
    return 0;
}

/*
There is nothing can stop us from hard working.
nothing stop working
hi st 

There is a cat in the box.

*/

第5题

#include<stdio.h>

const int maxn = 10010;
int n;
int a[maxn];
int b[maxn];

int qusort(int s[],int start,int end)   
{
    int i,j;    
    i=start;    
    j = end;    
    s[0]=s[start];    
    while(i<j)
    {
        while(i<j&&s[0]<s[j])
        j--;   
        if(i<j)
        {
            s[i]=s[j];   
            i++;    
        }
        while(i<j&&s[i]<=s[0])
            i++;   
        if(i<j)
        {
            s[j]=s[i];    
            j--;  
        }
    }
    s[i]=s[0];    
    if (start<i)
        qusort(s,start,j-1);    
    if (i<end)
        qusort(s,j+1,end);
    return 0;
}


int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    for(int j=1;j<=n;j++){
        scanf("%d",&b[j]);
    }
    qusort(a,1,n);
    qusort(b,1,n);
    int pos = 1;
    int cnt = 0;
    for(int i=1;i<=n;i++){
        if(a[i] > b[pos]){
            cnt++;
            pos++;
        }
    }
    printf("%d",cnt);
    return 0;
}
/*
6
2 13 26 33 45 9
3 8 30 15 18 40
*/

第6题

dfs暴力找最长的拓扑路径

#include<stdio.h>

const int maxn = 400;
int g[maxn][maxn];
int n;
int a[maxn];
int ans = 0;
int in[maxn];
int out[maxn];
int c;

void dfs(int x,int cur){
    if(x == c){
        if((cur-a[c]) > ans) ans = cur-a[c];
        return;
    }
    for(int i=1;i<=n;i++){
        if(i == x) continue;
        if(i!=c && out[i] == 0) continue;
        if(g[x][i] == 1){
            dfs(i,cur+a[i]);
        }
    }
}

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    int u,v;
    while(scanf("%d%d",&u,&v) && u!=-1 && v!=-1){
        if(g[u][v] == 0){
            g[u][v] = 1;
            in[v]++;
            out[u]++;
        }
    }
    scanf("%d",&c);
    if(in[c] == 0) printf("0");
    else{
        for(int i=1;i<=n;i++){
            if(i == c) continue;
            if(out[i] == 0) continue;
            dfs(i,a[i]);
        }
        printf("%d",ans);
    }
    return 0;
}

/*
4
8 12 16 10
1 2
2 3
4 2
1 3
-1 -1
3


3
8 12 16
1 2
1 3
-1 -1
3
*/

队友用拓扑排序做的

#include<iostream>
#include<stack>
#include<vector>
#include<algorithm>
#include<cmath>
#include<queue>
#include<cstring>
using namespace std;
typedef long long ll;
struct node{
    vector<int> zi;
    int day;
    int ind;
    int maxT;
    vector<int> last;
    int cost;
}sub[500];
vector<int> ans;
int n,c;
void toposort() {
    queue<int> q;
    for (int i = 1; i <=n; i++)
        if (sub[i].ind  == 0) q.push(i);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        ans.push_back(u);
        for(int i = 0;i<sub[u].last.size ();i++ ){
            int cur = sub[u].last[i];
            sub[u].maxT = max(sub[cur].cost,sub[u].maxT );
        }
        sub[u].cost = sub[u].day + sub[u].maxT ;
        sub[u].maxT = sub[u].cost ;
        for(int i = 0;i<sub[u].zi.size() ;i++ ){
            int cur = sub[u].zi[i];
            if(--sub[cur].ind == 0 ){
                q.push(cur);
            }
        }
    }
    return ;
}
int main(){
    cin>>n;
    for(int i = 1;i<=n;i++){
        int t;
        cin>>t;
        sub[i].day = t;
        sub[i].ind = 0;
        sub[i].maxT = 0;
        sub[i].cost = 0;
    }
    while(1){
        int a,b;cin>>a>>b;
        if(a == -1 && b == -1){
            break;
        }
        sub[a].zi.push_back(b);  
        sub[b].last.push_back(a);  
        sub[b].ind ++;
    }
    cin>>c;
    toposort();
    cout<<sub[c].cost - sub[c].day ;
    return 0;
}