第 45 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（上海），签到题5题

补题链接：https://codeforces.com/gym/102900
https://ac.nowcoder.com/acm/contest/9925/

G.Fibonacci

G. Fibonacci
time limit per test1 second
memory limit per test1024 megabytes
inputstandard input
outputstandard output
In mathematics, the Fibonacci numbers, commonly denoted as fn, is a sequence such that each number is the sum of the two preceding numbers, starting with 1 and 1. That is, f1=1,f2=1 and fn=fn−2+fn−1 (n≥3).

Thus, the beginning of the sequence is 1,1,2,3,5,8,13,21,… .

Given n, please calculate ∑ni=1∑nj=i+1g(fi,fj), where g(x,y)=1 when x⋅y is even, otherwise g(x,y)=0.

Input
The only line contains one integer n (1≤n≤109).

Output
Output one number – ∑ni=1∑nj=i+1g(fi,fj).

Examples
inputCopy
3
outputCopy
2
inputCopy
10
outputCopy
24
inputCopy
100
outputCopy
2739

题意：

• 给你一个数n（1e9），对于长位n的斐波那契数列的所有数对，如果x*y为偶数，那么贡献+1，求总的贡献。

思路：

• 不难发现斐波那契数列满足奇奇偶的规律，所以可以得到1-n中的奇数个数为n/3*2+n%3。
• 那么所有的对数n*(n-1)/2减去奇数的对数就是答案。

#include
using namespace std;
typedef long long LL;

int main(){
    LL n;  cin>>n;
    LL odd = n/3*2+n%3;  //奇数个数
    cout<<n*(n-1)/2-odd*(odd-1)/2<<"\n";
    return 0;
}
1
2
3
4
5
6
7
8
9
10

M.Gitignore

M. Gitignore
time limit per test1 second
memory limit per test1024 megabytes
inputstandard input
outputstandard output
Your git project (you don’t need to be familiar with git to solve this problem) has some files that should be ignored from synchronizing. You need to calculate the minimum number of lines needed for gitignore.

Formally, your project is a folder. A folder can have files and sub folders. There are no empty folders (i.e. folders without any files or sub folders inside). Initially, the git software will synchronize all the files in your project. However, you can specify some files and folders in the settings (which is called gitignore) to exclude them from synchronizing. For each line in gitignore, you can specify either a file or all the files in a folder. You can not ignore the whole project folder (i.e. an empty line in gitignore).

You are given paths for all the files in the project and whether they should be ignored or shouldn’t. Your task is to calculate the minimum number of lines for gitignore.

Input
The input contains several test cases. The first line contains a single positive integer T which is the number of test cases. For each test case, you are first given two non-negative numbers n and m. And then n non-empty lines of file paths that should be ignored, and m non-empty lines of file paths that should not be ignored.

The paths are strings containing lower-cased English alphabets and slashes (‘/’) only. Slashes are used to separate folders, sub folders and file name. For exapmle, “a/b/c/d” indicates folder “a” in the project folder, folder “b” in folder “a”, folder “c” in “b” and file “d” in folder “c”. All the paths are valid, specifically:

The path is non-empty and it always indicates a file (i.e. the path does not end with a slash).
The path does not start with a slash.
Folder names and file names are non-empty (i.e. there are no consecutive slashes).
File paths are always unique (i.e. all the paths in a test case are different).
In a folder, no sub folders and files share the same names. For example, there won’t be two files “a/b/a” and “a/b/a/d” in one test case. However, files “a/b/a” and “a/b/b” are allowed.
1≤n+m≤100 holds and in the whole input there are no more than 1,000 characters in file paths (i.e. the sum of lengths of file path strings in the whole input file is no more than 1,000).

Output
T lines of non-negative integers, the minimum number of gitignore lines for each test case.

Example
inputCopy
2
3 0
data/train
data/test
model
3 1
data/train
data/test
model
data/sample
outputCopy
2
3
Note
In the first sample test case, the corresponding gitignore file contains 2 lines: a folder line “data/” and a file name “model”.

In the second sample test case, the corresponding gitignore file contains 3 file lines: “data/train”, “data/test” and “model”.

题意：

• 给出n个需要删除的文件路径，m个不能删除的文件路径（保证没有文件名=文件夹名）
• 你可以通过1次删除一整个文件夹里所有的文件。 问最少需要删多少次。

思路：

• 先对n个路径建树，打上标记0。
• 再对m个路径建树，打上标记1。
• 最后从根遍历遇到第一个未标记返回1并累加即可。
• 不用真的建树，map维护一下每个节点的标记即可（对于不是第一次遇到的且没有打上1标记的文件夹，意味着里面的文件可以一起删除， 遇到一次答案-1，然后直接去判断下个文件即可。）

#include
using namespace std;
string s[110];
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T;  cin>>T;
    while(T--){
        int n, m;  cin>>n>>m;
        map<string, int>mp;
        int ans = n;
        for(int i = 1; i <= n+m; i++){
            cin>>s[i];
            string tmp = "";
            for(char ch : s[i]){
                if(ch!='/')tmp += ch;
                else{
                    if(i<=n)mp[tmp] = 0;
                    else mp[tmp] = 1;
                }
            }
        }
        for(int i = 1; i <= n; i++){
            string tmp = "";
            for(char ch : s[i]){
                if(ch!='/')tmp += ch;
                else{
                    if(mp[tmp]==1)continue;
                    else if(mp[tmp]==0)mp[tmp] = 2;
                    else if(mp[tmp]==2){
                        ans--;
                        break;
                    }
                }
            }
        }
        cout<<ans<<"\n";
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

B.Mine Sweeper II

B. Mine Sweeper II
time limit per test1 second
memory limit per test1024 megabytes
inputstandard input
outputstandard output
A mine-sweeper map X can be expressed as an n×m grid. Each cell of the grid is either a mine cell or a non-mine cell. A mine cell has no number on it. Each non-mine cell has a number representing the number of mine cells around it. (A cell is around another cell if they share at least one common point. Thus, every cell that is not on the boundary has 8 cells around it.) The following is a 16×30 mine-sweeper map where a flagged cell denotes a mine cell and a blank cell denotes a non-mine cell with number 0.

Given two mine-sweeper maps A,B of size n×m, you should modify at most ⌊nm2⌋ (i.e. the largest nonnegative integer that is less than or equal to nm2) cells in B (from a non-mine cell to a mine cell or vice versa) such that the sum of numbers in the non-mine cells in A and the sum of numbers in the non-mine cells in B are the same. (If a map has no non-mine cell, the sum is considered as 0.)

If multiple solutions exist, print any of them. If no solution exists, print “-1” in one line.

Input
The first line contains two integers n,m(1≤n,m≤1000), denoting the size of given mine-sweeper maps.

The i-th line of the following n lines contains a length-m string consisting of “.” and “X” denoting the i-th row of the mine-sweeper map A. A “.” denotes for a non-mine cell and an “X” denotes for a mine cell.

The i-th line of the following n lines contains a length-m string consisting of “.” and “X” denoting the i-th row of the mine-sweeper map B. A “.” denotes for a non-mine cell and an “X” denotes for a mine cell.

Output
If no solution exists, print “-1” in one line.

Otherwise, print n lines denoting the modified mine-sweeper map B. The i-th line should contain a length-m string consisting of “.” and “X” denoting the i-th row of the modified map B. A “.” denotes for a non-mine cell and an “X” denotes for a mine cell.

Please notice that you need not print the numbers on non-mine cells since these numbers can be determined by the output mine-sweeper map.

Example
inputCopy
2 4
X…X
X.X.
X.X.
.X…
outputCopy
X.XX
.X…
Note
We modify one cell in B. Then the sums of the numbers on non-mine cells in A and B both equal 10.

题意：

• 扫雷规则：给你一个n×m的矩阵，X代表雷，.代表没有雷。为X的点权值为0，为.的点权值为相邻八个的是雷(X)的数目。
• 对于每个矩阵，定义sum为矩阵中所有点的点权和。 每次操作可以修改.->X 或则X->.。
• 现在给你两个图A和图B，求B能否通过不超过nm/2次修改成一个sum值与A相同的图，输出修改后的B图。

思路：

• 考虑每次修改任意一个点，不难发现周围8个点的权值都会发生变化，所以要搜索之类的，每次状态转移都要考虑修改很多的数据，复杂度较高。
• 进一步考虑修改造成的变化，X对sum没有贡献，只需考虑.。 假设某个点与周围8个中的x个X形成x个一一对应的关系，如果把.改X，X改.，那么对应关系的数量是不变的，即对sum的贡献是不变的。因此A图等价于A图中所有X和.互换的结果。
• 不难发现，这两个等价A图中，因为有一个是补图，一定有一个可以让B在nm/2次中成功转换（设改成第一个需要x>nm/2次，那么改成另一个的次数y=nm-x，肯定是

#include
using namespace std;
const int maxn = 1010;
char a[maxn][maxn], b[maxn][maxn];
int main(){
    int n, m;  cin>>n>>m;
    for(int i = 1; i <= n; i++)cin>>a[i]+1;
    for(int i = 1; i <= n; i++)cin>>b[i]+1;
    int cnt = 0;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(a[i][j] != b[i][j])cnt++;
        }
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(cnt<n*m/2)cout<<a[i][j];
            else{
                cout<<(a[i][j]=='X' ? '.' : 'X');
            }
        }
        cout<<"\n";
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

D.Walker

D. Walker
time limit per test1 second
memory limit per test1024 megabytes
inputstandard input
outputstandard output
As a world-famous traveler, Prof. Pang’s research interest is to travel as many places as possible in his life.

We have a segment [0,n]. There are two travelers on it. The first one is on position p1 with velocity v1 (which means s/he can walk v1 unit on the segment per second). The second one is on position p2 with velocity v2.

From their respective beginning points, travelers can walk on the segment. They cannot walk outside the segment. Whenever they want to change their direction, they can turn around immediately.

Please help Prof. Pang to calculate the minimum possible time by which every position of the segment is passed by at least one traveler.

Input
The first line contains one integer test (1≤test≤10000) – the number of test cases.

The i-th of the next test lines contains five numbers n,p1,i,v1,i,p2,i,v2,i (0digits after the decimal point.

Output
For each test case, we should output one number – the minimum time that every position of the segment is passed by at least one traveler.

Your answer is considered correct if its absolute or relative error does not exceed 10−6.

Example
inputCopy
2
10000.0 1.0 0.001 9999.0 0.001
4306.063 4079.874 0.607 1033.423 0.847
outputCopy
5001000.0000000000
3827.8370013755

题意：

• 在一个长为n的路上，在d1,d2两个位置有两个人速度为v1,v2，走到墙壁会反弹。
• 求最少需要多长时间能够至少在每个位置都被人走过。

思路：

• 因为没给方向，所以对方向分类讨论，4种情况。（设p1在p2左边）
• p1与p2相向而行：ans=max((n-d1)/v1,d2/v2)
  都往p2的右走/都往p1的左走：ans=min((min(d1,n-d1)+n)/v1,(min(d2,n-d2)+n)/v2)
• p1与p2反向而行：
  二分时间，check判断能否在规定时间内走完。
  或者二分相遇点，计算需要的时间，check判断是否保留，跑1000次二分取min。

#include
using namespace std;
double eps = 1e-9;

double n, d1, v1, d2, v2;
double check(double mid){ //判断mid时间能否跑完
    double p1 = max(mid*v1-2*d1, (mid*v1-d1)/2)+d1;
    double p2 = max(mid*v2-2*(n-d2), (mid*v2-(n-d2))/2)+(n-d2);
    return p1+p2>=n;
}

int main(){
    int T;  cin>>T;
    while(T--){
        cin>>n>>d1>>v1>>d2>>v2;
        if(d1 > d2){ swap(d1, d2); swap(v1, v2); }
        double ans = 0;
        //往两边走
        double x1 = min(n-d1, d1)+n, x2 = min(n-d2, d2)+n;
        ans = min(x1/v1, x2/v2);
        //相向而行
        ans = min(ans, max((n-d1)/v1, d2/v2));
        //反向而行, 二分时间
        double l = max(d1/v1, (n-d2)/v2), r = ans;
        while(abs(r-l) > eps){
            double mid = (l+r)/2;
            if(!check(mid))l = mid;
            else {
                r = mid, ans = min(ans, mid);
            }
        }
        printf("%.10lf\n", ans);
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

I.Sky Garden

I. Sky Garden
time limit per test1 second
memory limit per test1024 megabytes
inputstandard input
outputstandard output
Prof. Du and Prof. Pang plan to build a sky garden near the city of Allin. In the garden, there will be a plant maze consisting of straight and circular roads.

On the blueprint of the plant maze, Prof. Du draws n circles indicating the circular roads. All of them have center (0,0). The radius of the i-th circle is i.

Meanwhile, Prof. Pang draws m lines on the blueprint indicating the straight roads. All of the lines pass through (0,0). Each circle is divided into 2m parts with equal lengths by these lines.

Let Q be the set of the n+m roads. Let P be the set of all intersections of two different roads in Q. Note that each circular road and each straight road have two intersections.

For two different points a∈P and b∈P, we define dis({a,b}) to be the shortest distance one needs to walk from a to b along the roads. Please calculate the sum of dis({a,b}) for all {a,b}⊆P.

Input
The only line contains two integers n,m (1≤n,m≤500).

Output
Output one number – the sum of the distances between every pair of points in P.

Your answer is considered correct if its absolute or relative error does not exceed 10−6.

Examples
inputCopy
1 2
outputCopy
14.2831853072
inputCopy
2 3
outputCopy
175.4159265359
Note

dis(p1,p2)=dis(p2,p3)=dis(p3,p4)=dis(p1,p4)=π2
dis(p1,p5)=dis(p2,p5)=dis(p3,p5)=dis(p4,p5)=1
dis(p1,p3)=dis(p2,p4)=2

题意：

• 有n个同心圆，圆心为（0,0），第i个的半径为i。有m条直线，都通过（0,0），每个圆都被等分为2m部分。
• 令p为所有线的交点的集合，求所有dist（pi,pj）的距离之和，其中从pi到pj只能沿着圆或直线走。

思路：

• 当m=1时，没有圆心这个点，直接(1+2+3+…n)*2即可。
• 当m>1时，圆心也是交点，从圆心到其他所有点的距离为，每一条的1+2+3+…+n=(n+1)n/2乘上2m条， 为nm(n+1)。
• 考虑同一层内的点，可以选定一个点为基点，计算其他所有点到该点的距离（左半圆右半圆也是一样的，2次半径和弧长取最小，然后对称点单独算），因为每个点是等价的，所以最后*本层点数即可。
• 考虑层与层之间的点，可以从内层往外层算，可以维护本层1号点到本层及内部所有点的距离和，然后再从内层的1号点走层之间的路径往当前层转移即可，最后乘上当前层的点数即可。

#include
using namespace std;
const double pi = acos(-1);

int main(){
    double n, m;  cin>>n>>m;
    //本层1点到本层其余所有点的距离和，本层1点到本层及内部层所有点的距离和。
    double point[1500], cir[1500], hu = pi/m;
    double res = 0;
    if(m > 1)res += n*(n+1)*m; //圆心
    for(int i = 1; i <= n; i++){     //层
        for(int j = 1; j < m; j++){  //到（左半圆）
            point[i] += min(i*2.0, hu*j*i); //2次半径或走弧
        }
        point[i] *= 2;      //到（左半圆）
        point[i] += 2*i;    //到对称点（走直径）
        res += point[i]*m;  //m个点值都一样的
        res += ((i-1)*2*m+cir[i-1])*2*m;     //(内层1点到所有内部点的距离+层之间的距离)*本层点数
        cir[i] = cir[i-1]+(i-1)*2*m+point[i];//内层1点到所有点间的距离+层之间的距离+到本层所有点的距离
    }
    printf("%.10lf\n", res);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23