这套题是叉姐出的，好难啊，先扫一遍好像没有会做的题了，仔细一想好像D最容易哎

Super Resolution
Accepted : 112		Submit : 178
Time Limit : 1000 MS		Memory Limit : 65536 KB

Super Resolution

Bobo has an n×m picture consists of black and white pixels. He loves the picture so he would like to scale it a×b times. That is, to replace each pixel with a×b block of pixels with the same color (see the example for clarity).

Input

The input contains zero or more test cases and is terminated by end-of-file. For each test case,

The first line contains four integers n,m,a,b. The i-th of the following n lines contains a binary string of length m which denotes the i-th row of the original picture. Character "0" stands for a white pixel while the character "1" stands for black one.

1≤n,m,a,b≤10
The number of tests cases does not exceed 10.

Output

For each case, output n×a rows and m×b columns which denote the result.

Sample Input

Sample Output

水题直接开搞，就是我把图像放大m*n倍，那不就是周围都是它的重复了，循环搞下。

#include<stdio.h>

int main(){

int n,m,a,b;

while(~scanf("%d%d%d%d",&n,&m,&a,&b)){

getchar();

char s[];

while(n--){

gets(s);

for(int k=;k<a;k++){

for(int i=;i<m;i++){

    for(int j=;j<b;j++)

      printf("%c",s[i]);

}

printf("\n");

}}}

return ;}

然后我也没有会做的题了，群里讲I是脑洞题，我就直接开搞了

Strange Optimization
Accepted : 38		Submit : 209
Time Limit : 1000 MS		Memory Limit : 65536 KB

Strange Optimization

Bobo is facing a strange optimization problem. Given n,m, he is going to find a real number α such that f(12+α) is maximized, where f(t)=mini,j∈Z|i/n−j/m+t|. Help him!

Note: It can be proved that the result is always rational.

Input

The input contains zero or more test cases and is terminated by end-of-file.

Each test case contains two integers n,m.

1≤n,m≤109
The number of tests cases does not exceed 104.

Output

For each case, output a fraction p/q which denotes the result.

Sample Input

1 1

1 2

Sample Output

1/2

1/4

Note

For the first sample, α=0 maximizes the function.

这个题我好像不会哎，这个脑洞开的，1/（m*n*2），这是我第一次猜的，错了啊，接下来我的方向就是找i/n-j/m的最小区间了，毕竟后面的数是个实数，这个答案符合最小公倍数啊，交上去wa，后来才发现是爆int，知道了又发现这个OJ是int64，求心理面积大小

#include <stdio.h>

__int64 gcd(__int64 a,__int64  b)

{

    while(b != )

    {

    __int64 r = b;

    b = a % b;

    a = r;

    }

    return a;

}

int main()

{

    __int64 m,n;

    while(~scanf("%I64d%I64d",&n,&m)){

        printf("1/%I64d\n",m/gcd(n,m)*n*);

    }

    return ;

}

Highway
Accepted : 37		Submit : 151
Time Limit : 4000 MS		Memory Limit : 65536 KB

Highway

In ICPCCamp there were n towns conveniently numbered with 1,2,…,n connected with (n−1) roads. The i-th road connecting towns ai and bi has length ci. It is guaranteed that any two cities reach each other using only roads.

Bobo would like to build (n−1) highways so that any two towns reach each using only highways. Building a highway between towns x and y costs him δ(x,y) cents, where δ(x,y) is the length of the shortest path between towns x and y using roads.

As Bobo is rich, he would like to find the most expensive way to build the (n−1) highways.

Input

The input contains zero or more test cases and is terminated by end-of-file. For each test case:

The first line contains an integer n. The i-th of the following (n−1) lines contains three integers ai, bi and ci.

1≤n≤105
1≤ai,bi≤n
1≤ci≤108
The number of test cases does not exceed 10.

Output

For each test case, output an integer which denotes the result.

Sample Input

Sample Output

19

15

这个题似曾相识，先DFS两次求最长路，树的直径，和蓝桥杯大臣的旅费差不多，然后再其他点到这两个点最长的距离得和。我是做不出来

和hdu2916差不多

都是树形dp，那个题的代码

#include <bits/stdc++.h>

using namespace std;

int len;

int head[],dp[],id[],dp2[],id2[];

//dp[i],从i往下倒叶子的最大距离

//id，最大距离对应的序号

//dp2，次大距离

//id2，次大序号

struct node {

    int now,next,len;

} tree[];

void add(int x,int y,int z) { //建树

    tree[len].now = y;

    tree[len].len = z;

    tree[len].next = head[x];

    head[x] = len++;

    tree[len].now = x;

    tree[len].len = z;

    tree[len].next = head[y];

    head[y] = len++;

}

void dfs1(int root,int p) {

    //从节点root往下倒叶子节点的最大距离

    //p是root父节点

    int i,j,k,tem;

    dp[root] = ;

    dp2[root] = ;

    for(i = head[root]; i!=-; i = tree[i].next) {

        k = tree[i].now;

        if(k == p)//不能再找父节点

            continue;

        dfs1(k,root);

        if(dp2[root]<dp[k]+tree[i].len) { //比次大的要大

            dp2[root] = dp[k]+tree[i].len;

            id2[root] = k;

            if(dp2[root]>dp[root]) { //次大大于最大，交换其值与id

                swap(dp2[root],dp[root]);

                swap(id2[root],id[root]);

            }

        }

    }

}

//len为p到root的长度

void dfs2(int root,int p) {

    //从父亲节点开始更新

    int i,j,k;

    for(i = head[root]; i!=-; i = tree[i].next) {

        k = tree[i].now;

        if(k == p)

            continue;

        if(k == id[root]) { //最大距离的序号，对应的是dp[k]，多以这里要加次大的

            if(tree[i].len+dp2[root]>dp2[k]) {

                dp2[k] = tree[i].len+dp2[root];

                id2[k] = root;

                if(dp2[k]>dp[k]) {

                    swap(dp2[k],dp[k]);

                    swap(id2[k],id[k]);

                }

            }

        } else {

            if(tree[i].len+dp[root]>dp2[k]) {

                dp2[k] = tree[i].len+dp[root];

                id2[k] = root;

                if(dp2[k]>dp[k]) {

                    swap(dp2[k],dp[k]);

                    swap(id2[k],id[k]);

                }

            }

        }

        dfs2(k,root);

    }

}

int main() {

    int n,i,j,x,y;

    while(~scanf("%d",&n)) {

        len = ;

        memset(head,-,sizeof(head));

        for(i = ; i<=n; i++) {

            scanf("%d%d",&x,&y);

            add(i,x,y);

        }

        dfs1(,-);

        dfs2(,-);

        for(i = ; i<=n; i++)

            printf("%d\n",dp[i]);

    }

    return ;

}

巴特西

2017年湘潭邀请赛（湖南）or 江苏省赛