二、3.10 实践课

NOIP

hiho1700 相似颜色

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
int getVal(char ch){
    if (ch >= '0' && ch <= '9') return ch - '0';
    return ch - 'a' + 10;
}
int dist(int rgb, int col){
    rgb = rgb * 16 + rgb;
    return (rgb - col) * (rgb - col);
}
char getChar(int val){
    if (val < 10) return val + '0';
    return val + 'a' - 10;
}
int main(){
    char ch, ch1, ch2;
    scanf("%c", &ch);
    printf("%c", ch);
    for (int t = 0; t < 3; t++){
        scanf("%c%c", &ch1, &ch2);
        int num = getVal(ch1) * 16 + getVal(ch2);
        int Min = INF, ans = -1;
        for (int i = 0; i < 16; i++){
            if (dist(i, num) < Min){
                Min = dist(i, num);
                ans = i;
            }
        }
        printf("%c", getChar(ans));
    }
    puts("");
    return 0;
}

hdu6182 一道数学题

uva11462 年龄排序，注意内存

#include <cstdio>
#include <cstring>
using namespace std;
const int N = 111;
int n, cnt[N];
int main(){
    for (; scanf("%d", &n) == 1 && n;){
        memset(cnt, 0, sizeof cnt);
        for (int x;n--;){
            scanf("%d", &x);
            cnt[x]++;
        }
        bool first = true;
        for (int i = 1; i <= 100; i++){
            for (int j = 0; j < cnt[i]; j++){
                if (!first) printf(" ");
                first = false;
                printf("%d", i);
            }
        }
        puts("");
    }
    return 0;
}

hdu5773 The All-purpose Zero

很巧妙的智商题。意思是数列里的 0 可以替换成任何数。做法很巧妙，如果 a1 ai 中有 z 个 0 的话，就把 ai 当作 ai − z 处理。遇到 0 不处理，最后把答案数加上总的 0 的个数即可

#include<cstdio>
using namespace std;
const int N=1000010;
int s[N],top,num;
int Find(int x){
    int l=1,r=top;
    while (l<r){
        int mid=(l+r)>>1;
        if (s[mid]<=x)l=mid+1;
        else r=mid;
    }
    return l;
}
int main(){
    int T,n,x;
    scanf("%d",&T);
    for (int cas=1;cas<=T;cas++){
        scanf("%d",&n);
        num=0,top=0;
        s[0]=-100000007;
        for (;n--;){
            scanf("%d",&x);
            if (!x)num++;
            else {
                x-=num;
                if (x>s[top]) s[++top]=x;
                else s[Find(x)]=x;
            }
        }
        printf("Case #%d: %d\n",cas,top+num);
    }
    return 0;
} 

uva10954 优先队列

有n个数的集合S，每次可以从S中删除两个数，然后把它们的和放回集合，直到剩下一个数。每次操作的开销等于剩下的两个数之和，求解最小的总开销。

#include<cstdio>
#include<iostream>
#include<queue>
using namespace std;
int i,n,x;
int main(){
    //freopen("fuck.in","r",stdin);
    for(;scanf("%d",&n)==1&&n;){
        priority_queue<int,vector<int>, greater<int> >q;
        for (int i=1;i<=n;i++){scanf("%d",&x);q.push(x);}
        int ans=0;
        for (int i=1;i<n;i++){
            int x=q.top();q.pop();
            int y=q.top();q.pop();
            ans+=x+y;
            q.push(x+y);
        }
        printf("%d\n",ans);
    }
    return 0;
}

hdu5774 Where Amazing Happens

第一次看见这种题目吧

#include<cstdio>
#include<map>
#include<string>
#include<iostream>
using namespace std;
map<string,int>mp;
int a[100];
int main(){
    //freopen("fuck.in","r",stdin);
    mp["Cleveland Cavaliers"]=0; a[0]=1;
    mp["San Antonio Spurs"]=1;   a[1]=5;
    mp["Miami Heat"]=2;          a[2]=3;
    mp["Dallas Mavericks"]=3;    a[3]=1;
    mp["L.A. Lakers"]=4;         a[4]=11;
    mp["Boston Celtics"]=5;      a[5]=17;
    mp["Detroit Pistons"]=7;     a[7]=3;
    mp["Chicago Bulls"]=8;       a[8]=6;
    mp["Houston Rockets"]=9;     a[9]=2;
    mp["Philadelphia 76ers"]=10; a[10]=2;
    mp["Seattle Sonics"]=11;     a[11]=1;
    mp["Washington Bullets"]=12; a[12]=1;
    mp["Portland Trail Blazers"]=13;a[13]=1;
    mp["Golden State Warriors"]=14;a[14]=2;
    mp["New York Knicks"]=15;    a[15]=2;
    mp["Milwaukee Bucks"]=16;    a[16]=1;
    mp["St. Louis Hawks"]=17;    a[17]=1;
    mp["Philadelphia Warriors"]=18;a[18]=2;
    mp["Syracuse Nats"]=19;      a[19]=1;
    mp["Minneapolis Lakers"]=20; a[20]=5;
    mp["Rochester Royals"]=21;   a[21]=1;
    mp["Baltimore Bullets"]=22;  a[22]=1;
    int T,ans;
    string st;
    scanf("%d\n",&T);
    for (int cas=1;cas<=T;cas++){
        getline(cin,st);
        if (mp.find(st)==mp.end())ans=0;
        else ans=a[mp[st]];
        printf("Case #%d: %d\n",cas,ans);
    }
    return 0;
}