Codeforces Round #434 题解

题目链接：http://codeforces.com/contest/861

A. k-rounding

题意：有n,k两个数，求对于n 的 k-rounding 数，k-rounding数就是一个有k个后置零的可以被n整除的最小数。

解法：暴力模拟。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int main()
{
    LL n, k;
    scanf("%lld %lld", &n, &k);
    LL bas = n;
    LL two = 0, five = 0;
    while(n){
        if(n%5==0){
            n /= 5;
            five++;
        }
        else{
            break;
        }
    }
    while(n){
        if(n%2 == 0){
            n /= 2;
            two++;
        }
        else{
            break;
        }
    }
    LL ans = 1;
    LL kk = k;
    if(k >= five){
        k -= five;
    }
    else{
        k = 0;
    }
    if(kk >= two){
        kk -= two;
    }
    else{
        kk = 0;
    }
    for(LL i=1; i<=k; i++) ans = ans*5;
    for(LL i=1; i<=kk; i++) ans = ans*2;
    printf("%lld\n", ans*bas);
    return 0;
}

B. Which floor?

题意：有一幢大楼，大楼每层有相同数量的房间，假设大楼为无数层，房间号从下至上逐个增加，第一个房间的号码为1，已知m个房间所在层数，求房间号为 n 的房间所在层数。若不能确定房间所在层数，则输出”-1”。已知条件：1.每层楼有一个或多个房间2.每层楼的房间数量相同3.房间号为1的房间只能在1楼4.房间号从小到大递增

解法：将所有已知的条件放入，暴力枚举一下每层房间数(1-100)，找出可行的每层房间数，再算出房间n所在层数，看前后两个房间的楼层数是否出现矛盾。

#include <bits/stdc++.h>
using namespace std;
int n, m;
struct node{
    int k,f;
    node(){}
    node(int k, int f):k(k),f(f){}
    bool operator<(const node &rhs) const{
        return f<rhs.f;
    }
}a[110];
int main()
{
    scanf("%d %d", &n,&m);
    int mx = -1;
    for(int i=1; i<=m; i++){
        scanf("%d %d", &a[i].k,&a[i].f);
        mx = max(mx, a[i].k);
    }
    sort(a+1,a+m+1);
    int ans = 0;
    int id = 0;
    for(int i=1; i<=100; i++){
        int j;
        for(j=1; j<=m; j++){
            if(a[j].k >= (a[j].f-1)*i+1 && a[j].k <= a[j].f*i){
                continue;
            }
            else{
                break;
            }
        }
        if(j>m){
            if(id==0){
                ans++;
                id=i;
            }
            else{
                if(n/id+(n%id!=0) != n/i+(n%i!=0)){
                    ans++;
                    id = i;
                }
            }
        }
    }
    if(ans==1){
        printf("%d\n", n/id+(n%id!=0));
    }
    else{
        printf("-1\n");
    }
    return 0;
}

C. Did you mean...

题意：a e i o u是元音，在一个字符串里不能有3个连续的辅音，但是3个及以上相同的连续辅音可以，否则就要用空格隔开，给你字符串，用最少的空格把字符串变为合法。

解法：暴力模拟。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 3010;
vector <char> v[maxn];
string s;
bool check(char c){
    if(c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') return true;
    return false;
}
int main()
{
    cin >> s;
    int n = s.size();
    int cnt = 0;
    int len = 0;
    for(int i=0; i<n; i++){
        if(check(s[i])){
            len = 0;
            v[cnt].push_back(s[i]);
        }
        else{
            if(len>=2){
                bool flag = 1;
                for(int j=i; j>=i-2; j--){
                    if(s[j] != s[i]){
                        flag = 0;
                        break;
                    }
                }
                if(flag == 0){
                    cnt++;
                    v[cnt].push_back(s[i]);
                    len = 0;
                }
                else{
                    v[cnt].push_back(s[i]);
                }
            }
            else{
                v[cnt].push_back(s[i]);
            }
            len++;
        }
    }
    for(int i=0; i<=cnt; i++){
        for(int j=0; j<v[i].size(); j++){
            cout << v[i][j];
        }
        cout << " ";
    }
    cout << endl;
    return 0;
}

D. Polycarp's phone book

题意：给你一些电话号码，让你找出每一个电话号码的最短的子串，能唯一的找到这个电话号码，就是找出每个串的最短且不是其他串的子串的子串。

解法：可以用字典树存下每个串的所有后缀（插入的时候把每个后缀的所有前缀的个数都记录），然后查询的时候对于一个串的所有后缀，找出字典树中第一个不存在于其他串中的前缀，然后取长度最短的那个。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000010;
const int maxs = 10;
int root, sz, ch[maxn][maxs], val[maxn];
char ans[20];
int maxlen;
vector <int> v[20];
int newnode(){
    memset(ch[sz], -1, sizeof(ch[sz]));
    return sz++;
}
void init(){
    sz = 0;
    root = newnode();
}
int getid(char x){
    return x-'0';
}
void Insert(char *s){
    int now = root;
    int len = strlen(s);
    for(int i=0; i<len; i++){
        int go = getid(s[i]);
        if(ch[now][go] == -1){
            ch[now][go] = newnode();
        }
        v[go].push_back(ch[now][go]);
        val[ch[now][go]]++;
        now = ch[now][go];
    }
}
void Delete(char *s){
    int now = root;
    int len = strlen(s);
    for(int i=0; i<len; i++){
        int go = getid(s[i]);
        val[ch[now][go]]--;
        now = ch[now][go];
    }
}
void query(char *s){
    int now = root;
    int len = strlen(s);
    int curlen = 0;
    char temp[20];
    for(int i=0; i<len; i++){
        int go = getid(s[i]);
        now = ch[now][go];
        temp[curlen++] = s[i];
        if(val[now] == 0){
            if(curlen < maxlen){
                maxlen = curlen;
                temp[curlen] = '\0';
                strcpy(ans, temp);
                break;
            }
        }
    }
}
char s[70010][10];
int main()
{
    int n;
    scanf("%d", &n);
    init();
    for(int i=0; i<n; i++){
        scanf("%s", s[i]);
        for(int j=0; j<9; j++) Insert(s[i]+j);
    }
    for(int i=0; i<n; i++){
        maxlen = 10;
        for(int j=0; j<9; j++) Delete(s[i]+j);
        for(int j=0; j<9; j++) query(s[i]+j);
        for(int j=0; j<9; j++) Insert(s[i]+j);
        printf("%s\n", ans);
    }
    return 0;
}

E. Tests Renumeration

没补。

F. Wizard's Tour

题意：给出一张无向图,要求找出尽量多的长度为2的不同路径(边不可以重复使用,点可以重复使用)

解法：神题ORZ。这道题是BZOJ上面的4874改的。不会做啊，膜了一发题解。http://www.cnblogs.com/liu-runda/p/7542312.html。然后可以这样做：首先猜测,一个连通块内,如果是偶数条边,那么所有边都可以用上.如果是奇数条边,那么只会剩下一条边.只要给出一个方案构造的方法,那么正确性就可以从构造方法中得出.
长度为2的路径中中间那个点和两条边都有关.我们可以认为这两条边都属于中间那个点. 于是现在就变成把每条边分配给它的两个端点中的一个.显然,一个连通块最多只能有一个端点被分配奇数条边.构造方法是这样的:从连通块里拎出一棵生成树,然后把非树边随便分配,接下来从叶节点往上,依次分配所有非树边,从下到上依次确保每个点都被分配了偶数条边.最后除了根节点之外的点一定都被分配了偶数条边,根节点被分配的边数奇偶性和连通块内总边数的奇偶性相同。

//CF 861F
#include <bits/stdc++.h>
using namespace std;
const int maxn = 200010;
struct edge{
    int to, next, num;
}E[maxn*2];
int edgecnt, head[maxn];
void init(){
    edgecnt = 1;
    memset(head, -1, sizeof(head));
}
void addedge(int u, int v, int w){
    E[edgecnt].to = v, E[edgecnt].next = head[u], E[edgecnt].num = w, head[u] = edgecnt++;
}
int n, m, u[maxn], v[maxn], typ[maxn];//typ[i]==0代表属于u[i]
int sum[maxn];
int fa[maxn];
bool ontree[maxn];
int find_set(int x){
    if(x == fa[x]) return x;
    else return fa[x] = find_set(fa[x]);
}
void union_set(int x, int y){
    int fx = find_set(x);
    int fy = find_set(y);
    if(fx!=fy){
        fa[fx] = fy;
    }
}
void dfs(int x, int pre){
    for(int i=head[x]; ~i; i=E[i].next){
        int to = E[i].to, id = E[i].num;
        if(to == pre) continue;
        dfs(to, x);
        if(sum[to] == 0){
            typ[id] = (v[id]==x);
            sum[x] ^= 1;
        }
        else{
            typ[id] = (u[id]==x);
            sum[to] = 0;
        }
    }
}
vector <int> P[maxn];
int main(){
    init();
    scanf("%d %d", &n,&m);
    for(int i=1; i<=m; i++){
        scanf("%d %d", &u[i],&v[i]);
    }
    for(int i=1; i<=n; i++) fa[i] = i;
    for(int i=1; i<=m; i++){
        if(find_set(u[i])==find_set(v[i])){
            typ[i]=0;
            sum[u[i]]^=1;
        }
        else{
            union_set(u[i], v[i]);
            addedge(u[i], v[i], i);
            addedge(v[i], u[i], i);
        }
    }
    for(int i=1; i<=n; i++){
        if(i==fa[i]) dfs(i, 0);
    }
    for(int i=1; i<=m; i++){
        if(typ[i]==0) P[u[i]].push_back(v[i]);
        else P[v[i]].push_back(u[i]);
    }
    int ans = 0;
    for(int i=1; i<=n; i++){
        ans += P[i].size()/2;
    }
    printf("%d\n", ans);
    for(int i=1; i<=n; i++){
        int sz = P[i].size();
        for(int j=0; j+1<sz; j+=2){
            printf("%d %d %d\n", P[i][j], i, P[i][j+1]);
        }
    }
    return 0;
}