HZNU 2019 Summer training 3

比眉伴天荒 2021-11-11 15:50 221阅读 0赞

## A - Brain's Photos ##

CodeForces - 707A

题意：判断是不是彩色

题解：判断是否含有除 B W G 以外的英文字母即可

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <iostream>
    #include <cstdio>
    #include <cmath>
    #include <cstring>
    #include <algorithm>
    #include <vector>
    #include <queue>
    #include <set>
    #include <map>
    #define INF 0x3f3f3f3f
    #define lowbit(x) (x&(-x))
    using namespace std;
    typedef long long ll;
    
    const int maxn = 1e4+7;
    
    
    int main()
    {
        int n,m;
        scanf("%d %d",&n,&m);
        int flag = 1;
        getchar();
        for (int i=0;i<n;i++)
        {
            string s;
            getline(cin,s);
            for(int i=0;i<s.size();i++)
                if(s[i] != 'B' && s[i] != 'W' && s[i] != ' ' && s[i] != 'G')
                    flag = 0;
           // cout<<s<<endl;
        }
        if(flag)
            puts("#Black&White");
        else
            puts("#Color");
    }

## B - Bakery ##

CodeForces - 707B

题意：n个城市，m条边，k个城市里有进货点。Masha要选一个没有进货点的城市开店，要选一个最近的有商店的城市进货，输出她进货时所用的最小路程。

题解：进货点和商店相邻最优然后对每个进货点扫一次就行

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <iostream>
    #include <cstdio>
    #include <cmath>
    #include <cstring>
    #include <algorithm>
    #include <vector>
    #include <queue>
    #include <set>
    #include <map>
    #define INF 0x3f3f3f3f
    #define lowbit(x) (x&(-x))
    using namespace std;
    typedef long long ll;
    
    const int maxn = 1e5+7;
    
    int u[maxn];
    int v[maxn];
    int l[maxn];
    map<int,int>mp;
    int main()
    {
        int n,m,k;
        scanf("%d %d %d",&n,&m,&k);
        for(int i=0;i<m;i++)
        {
            scanf("%d %d %d",&u[i],&v[i],&l[i]);
        }
        int no;
        for(int i=0;i<k;i++)
        {
            scanf("%d",&no);
            mp[no] = 1;
        }
        int ans = INF;
        for(int i=0;i<m;i++)
        {
            if(mp[u[i]] + mp[v[i]] == 1)
                ans = min(ans,l[i]);
        }
        printf("%d\n",ans == INF ? -1 : ans);
    }

## C - Pythagorean Triples ##

CodeForces - 707C

题意：给出一条变，要求你给出另外两条构成直角三角形

题解：a2 \+ b2  = c2 可得 a2 = (c + b) \* (c - b)。如果给的a为奇数的话，那么使得c - b = 1,c + b = a即可。如果a为偶数的话使得 c - b = 2,c + b = a \* a / 2即可，化简即可。注意特殊样例 a <= 2

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <iostream>
    #include <cstdio>
    #include <cmath>
    #include <cstring>
    #include <algorithm>
    #include <vector>
    #include <queue>
    #include <set>
    #include <map>
    #define INF 0x3f3f3f3f
    #define lowbit(x) (x&(-x))
    using namespace std;
    typedef long long ll;
    
    const int maxn = 1e4+7;
    
    
    int main()
    {
        ll n,c,b;
        while(~scanf("%lld",&n)) {
            if (n <= 2)
                puts("-1");
            else if (n % 2 == 0) {
                c = n * n / 4 + 1;
                b = c - 2;
                printf("%lld %lld\n", b, c);
            } else {
                c = (n * n + 1) / 2;
                b = c - 1;
                printf("%lld %lld\n", b, c);
            }
        }
    }

## D - Persistent Bookcase（DFS树） ##

CodeForces - 707D

题意：

有一个书架，书架有n层（分别编号为1…n），每层能放m本书（分别编号为1…m），有q次操作(分别编号为1…q）：  
1 i j：在第i层第j位放一本书（如果这个位置没有书）  
2 i j ：在第i层第j位取走一本书（如果这个位置有书）  
3 i:翻转第i行（无书变有书，有书变无书）  
4 k:回退到第k个操作后的状态，若k=0则为清空  
输出每次操作后书架上有几本书。

题解：妙啊，用book的二维数组模拟书架，按照顺序建树，操作1 2 3 显然都是在上一步的基础上进行的，只需要直接向前一步连接就行，操作4就是直接连向那个顶点，之后dfs遍历这棵树，同时更新每一个节点的数目即可。妙啊 ！

样例：

19 16 14

3 10

3 8

3 3

2 5 3

1 7 15

4 0

2 11 2

1 16 3

3 13

1 13 3

4 9

1 5 11

3 1

按照操作的顺序得：

![1468777-20190707174312886-2059295575.png][]

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<cmath>
    #include<vector>
    using namespace std;
    #define ll long long
    
    const int maxn = 1e5 + 10;
    const int INF = 0x3f3f3f3f;
    
    struct node{
        int type,i,j;
        int ans;
    }q[maxn];
    bool book[1005][1005];
    vector<int>g[maxn];
    int n,m,query;
    
    void dfs(int t,int cur){
        q[t].ans = cur;
        for(int i=0;i<g[t].size();i++){
            int next = g[t][i];
            if(q[next].type == 1){
                if(book[q[next].i][q[next].j])
                    dfs(next,cur);
                else {
                    book[q[next].i][q[next].j] = true;
                    dfs(next,cur + 1);
                    book[q[next].i][q[next].j] = false;
                }
            }
            else if(q[next].type == 2){
                if(!book[q[next].i][q[next].j])
                    dfs(next,cur);
                else{
                    book[q[next].i][q[next].j] = false;
                    dfs(next,cur - 1);
                    book[q[next].i][q[next].j] = true;
                }
            }
            else if(q[next].type == 3){
                int tot = 0;
                for(int j=1;j<=m;j++){
                    if(book[q[next].i][j]){
                        book[q[next].i][j] = false;
                        tot--;
                    }
                    else{
                        book[q[next].i][j] = true;
                        tot++;
                    }
                }
                dfs(next,cur + tot);
                for(int j=1;j<=m;j++)
                    book[q[next].i][j] = !book[q[next].i][j];
            }
            else{
                dfs(next,cur);
            }
        }
    }
    int main()
    {
        memset(book,false,sizeof book);
        q[0].ans = 0;
        scanf("%d %d %d",&n,&m,&query);
        for(int i=1;i<=query;i++){
            scanf("%d",&q[i].type);
            if(q[i].type <= 2){
                g[i-1].push_back(i);
                scanf("%d %d",&q[i].i,&q[i].j);
            }
            else if(q[i].type == 3){
                g[i-1].push_back(i);
                scanf("%d",&q[i].i);
            }
            else{
                scanf("%d",&q[i].i);
                g[q[i].i].push_back(i);
            }
        }
        dfs(0,0);
        for(int i=1;i<=query;i++)
            printf("%d\n",q[i].ans);
    }

## E - Garlands ##

CodeForces - 707E

题意：一个n \* m矩阵，k条链(1 <= n,m,k <= 2000)，每条链绑定着一些灯泡，每个灯泡亮着时有权值，灭掉的时候权值为0。一个链条控制其上所有灯泡的亮灭。有两种操作，SWITCH i：按第i条链的开关，开变关，关变开。ASK x1,y1,x2,y2，查询以x1,y1为左上，x2,y2为右下的矩阵的权值。ASK最多2000次

题解：2000 \* 2000 的数据可以使用二维的树状数组，主要是链的保证状态，当状态改变的时候如果关变开明显是加上顶点值，反之减去。在计算矩形的所有顶点值的和时候容斥一下面积就好了

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <iostream>
    #include <cstdio>
    #include <cmath>
    #include <cstring>
    #include <algorithm>
    #include <vector>
    #include <queue>
    #include <set>
    #include <map>
    #include<stack>
    #define INF 0x3f3f3f3f
    #define lowbit(x) (x&(-x))
    using namespace std;
    typedef long long LL;
    
    const int MAXN = 2e3 + 10;
    const int MOD = 1e9 + 7;
    
    int n,m,k;
    LL c[MAXN][MAXN];
    struct node
    {
        int len,x,y;
        LL w;
    }Q[MAXN][MAXN];
    int isOn[MAXN * MAXN],last[MAXN * MAXN];
    void init()
    {
        memset(c,0,sizeof c);
        for(int i = 1; i <= n * n; i++)
            isOn[i] = last[i] = 1;
    }
    
    void add(int x,int y,LL val)
    {
        for(int i = x; i <= n; i += lowbit(i))
            for(int j = y;j <= m; j += lowbit(j))
                c[i][j] += val;
    }
    
    LL ask(int x,int y)
    {
        LL ans = 0;
        for(int i = x; i > 0; i -= lowbit(i))
            for(int j = y; j > 0;j -= lowbit(j))
                ans += c[i][j];
        return ans;
    }
    LL all(int x1,int y1,int x2,int y2)
    {
        LL ans = ask(x2,y2) - ask(x2,y1 - 1) - ask(x1 - 1,y2) + ask(x1 - 1,y1 - 1);
        return ans;
    }
    int main()
    {
        scanf("%d %d %d",&n,&m,&k);
        init();
        for(int i = 1; i <= k; i++)
        {
            scanf("%d",&Q[i][0].len);
            for(int j = 1; j <= Q[i][0].len; j++)
            {
                scanf("%d %d %lld",&Q[i][j].x,&Q[i][j].y,&Q[i][j].w);
                add(Q[i][j].x,Q[i][j].y,Q[i][j].w);
            }
        }
        int query;
        scanf("%d",&query);
        char str[50];
        while(query--)
        {
            scanf("%s",str);
            if(str[0] == 'A')
            {
                for(int i = 1; i <= k; i++)
                {
                    if(last[i] != isOn[i])//last和isOn不相同保证了这条链被动过
                    {
                        for(int j = 1; j <= Q[i][0].len; j++)
                        {
                            if(isOn[i])
                                add(Q[i][j].x,Q[i][j].y,Q[i][j].w);//isOn为1代表原先为0，那么这条链上的每一个点都要加上权值
                            else
                                add(Q[i][j].x,Q[i][j].y,-Q[i][j].w);//如果isOn为0代表这条链是关闭的，这条链上的每一个点都减去权值
                        }
                        last[i] = isOn[i]; //将该条链的状态保证，以至于下次改变状态的时候可以知道和原先的状态是不一样的
                    }
                }
                int x1,y1,x2,y2;
                scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
                printf("%lld\n",all(x1,y1,x2,y2));
            }
            else
            {
                int tk;
                scanf("%d",&tk);
                isOn[tk] ^= 1;  //改变这条链的现有的状态
            }
    
        }
        return 0;
    }

转载于:https://www.cnblogs.com/smallhester/p/11147046.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211109/7ff090e0f46c40798ca686acd6f7a163.png
[1468777-20190707174312886-2059295575.png]: /images/20211109/6531f7c6061644edb1570be5473db4a4.png