A - 111 - CodeForces - 659A

题意

一个人绕着圆柱体建筑走路，每个点按序标号，给出正数就往标号大的方向走，负数就往标号小的方向走，问最后停在哪

思路

这题挂了一遍就是对我抢时间连题目都没好好看的惩罚QAQ
很简单，注意负数情况不要搞错就行

代码

#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

int n, a, b;

int main()
{
    cin >> n >> a >> b;
    if (b < 0) a += 100 * n;
    int ans = abs((a + b) % n);
    if (ans == 0) ans = n;
    cout << ans;
    return 0;
}

B - 扣1 - CodeForces - 740B

题目链接

题意

从序列中取出若干子序列，再从子序列中选择若干个，要求让原序列中的每个数乘他们选择的子序列里出现的次数之和最大

思路

也很简单，一眼看出是前缀和加差分，然后按这个思路做就没问题

代码

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;

int n, m;
int a[N];
int l, r;

int d[N];
int s[N];

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) cin >> a[i];
    s[1] = a[1];
    for (int i = 2; i <= n; i ++ ) s[i] = s[i - 1] + a[i];
    for (int i = 0; i < m; i ++ )
    {
        cin >> l >> r;
        if (s[r] - s[l - 1] > 0)
        {
        	d[l] ++ ;
        	d[r + 1] -- ;
        }
    }
    for (int i = 1; i <= n; i ++ ) d[i] += d[i - 1];
    int ans = 0;
    for (int i = 1; i <= n; i ++ ) ans += a[i] * d[i];
    cout << ans;
    return 0;
}

C - 拱坝 - CodeForces - 707B

题目链接

题意

给定一个无向带权图，标出若干个特殊点，求特殊点之外离任意一个特殊点最近的点到该特殊点的距离

思路

有点类似Kruskal的简化版？把特殊点放在一个点集，其余点各成点集，按边权从小到大排序，找到第一个连接一个特殊点和一个普通点的边输出权值即可

代码

 #include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>

using namespace std;

const int N = 100010;

struct Edge
{
    int a, b, w;
    bool operator< (const Edge &W) const
    {
        return w < W.w;
    }
}edges[N];

int n, m, k;
int p[N];

int main()
{
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i ++ ) p[i] = i;
    for (int i = 0; i < m; i ++ )
    {
        cin >> edges[i].a >> edges[i].b >> edges[i].w;
    }
    for (int i = 0; i < k; i ++ )
    {
        int u;
        cin >> u;
        p[u] = 0;
    }
    sort(edges, edges + m);
    for (int i = 0; i <= m; i ++ )
    {
        int a = edges[i].a, b = edges[i].b, w = edges[i].w;
        if ((p[a] == 0 && p[b] != 0) || (p[b] == 0 && p[a] != 0))
        {
            cout << w;
            return 0;
        }
    }
    cout << -1;
    return 0;
}

D - 河坝 - CodeForces699C

题目链接

题意

每天记为0 / 1 / 2 / 3, 0 表示休息，1 表示可以打比赛，2 表示可以锻炼，3 表示既可以打比赛也可以锻炼，不能连续两天打比赛 or 连续两天锻炼，有一个人不想休息，问休息天数最小是多少

思路

这题赛时给我整崩溃了，思路错了整场都没反应过来，比赛时光想着贪心了，实际用二维dp啊啊
q[i][j]表示第 i 天干第 j 件事的情况下，前 i 天不休息的天数最大值
然后就看代码吧~

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 110;

int n;
int a[N];
int q[N][N];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ ) cin >> a[i];
    for (int i = 1; i <= n; i ++ )
    {
        if (a[i] == 0)
        {
            q[i][0] = max({q[i - 1][1], q[i - 1][2], q[i - 1][0]});
        }
        else if (a[i] == 1)
        {
            q[i][1] = max(q[i - 1][0] + 1, q[i - 1][2] + 1);
            q[i][0] = max({q[i - 1][0], q[i - 1][1], q[i - 1][2]});
        }
        else if (a[i] == 2)
        {
            q[i][2] = max(q[i - 1][0] + 1, q[i - 1][1] + 1);
            q[i][0] = max({q[i - 1][0], q[i - 1][1], q[i - 1][2]});
        }
        else
        {
            q[i][1] = max(q[i - 1][0] + 1, q[i - 1][2] + 1);
            q[i][2] = max(q[i - 1][0] + 1, q[i - 1][1] + 1);
            q[i][0] = max({q[i - 1][0], q[i - 1][1], q[i - 1][2]});
        }
    }
    int ans = max({q[n][0], q[n][1], q[n][2]});
    cout << n - ans;
}

E - 和蔼! - CodeForces - 659E

题目链接

题意

把给定无向图的每条边换成有向边，问最少有多少个点没有入边

思路

问入边就直接想到顶点的度了
先把无向图每个顶点的度存下来，先找到度为 1 的点存进队列，让这个点连接的这条边直接指向这个点，将被指向的点度赋为无穷大，另一个点度数减去 1，最后再更新度为 1 的点存进队列，队列为空时判断有多少点度为 0，这个数量就是答案（因为度为 1 ，主动被指向的点都被赋为无穷大了，度为 0 的只能是没有被指向的）

代码

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

typedef pair<int, int> PII;

const int N = 100010;
const int inf = 0x3f3f3f;

int n, m;
vector<int> g[N];
int d[N];
queue<int> q;
int ans;

int main()
{
    cin >> n >> m;
    for (int i = 0; i < m; i ++ )
    {
        int a, b;
        cin >> a >> b;
        d[a] ++ ;
        d[b] ++ ;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    for (int i = 1; i <= n; i ++ )
    	if (d[i] == 1) q.push(i);
    while (q.size())
    {
        int t = q.front();
        q.pop();
        
        if (d[t] == 1)
            for (int i = 0; i < g[t].size(); i ++ )
            {
                if (g[t][i] != 0)
                {
                    int p = g[t][i];
                    for (int i = 0; i < g[p].size(); i ++ )
                    {
                        if (g[p][i] == t)
                        {
                            g[p][i] = 0;
                            d[t] = inf;
                            d[p] -- ;
                            if (d[p] == 1) q.push(p);
                            break;
                        }
                    }
                    break;
                }
            }
    }
    for (int i = 1; i <= n; i ++ )
    {
        if (d[i] == 0) ans ++ ;
    }
    cout << ans;

    return 0;
}

F - 抽象 - CodeForces - 740C

题目链接

题意

给定长度序列中取出任意子序列，要求所有子序列中未出现的最小非负整数值最大，输出最大值并构造序列

思路

赛时被 D 题整到崩溃甚至都没花太多时间想这题，最后想到个有点小麻烦的思路，但是时间不够了没能敲完，回去洗衣服洗到一半脑子一嗡忽然知道这题怎么做了，太弱智了！！！

首先输出的最大值一定是给出的所有序列中最短的那个序列的长度 + 1

为什么呢？因为想让未出现的最小非负整数最大，那肯定是从小到大填充序列，但是比如说最短的那个子序列长度是 2 ，那么两个位置分别填上 0 1，未出现的值一定是 2，最大值也只能是 2，因为已经没有比这么填更好的方式了

然后！重点是怎么构造序列！！！

我一开始想得太复杂了，哪个序列怎么填充给自己绕的晕头转向，但是后来突然想到，从前到后直接按顺序填 0 - 最大的非负整数不就可以了吗TAT，这样不管怎么取子序列都是满足条件的啊…

然后就AC啦~

代码

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 100010;

int n, m, l, r;
int d[N], a[N];
int ans;

int main()
{
    cin >> n >> m;
    for (int i = 0; i < m; i ++ )
    {
        cin >> l >> r;
        d[i].first = lr[i].second - lr[i].first;
    }
    sort(d, d + m);
    ans = d[0];
    cout << ans + 1 << endl;
    int k = 0;
    for (int i = 0; i < n; i ++ )
    {
        cout << k << ' ';
        k ++ ;
        if (k > ans) k = 0;
    }
    return 0;
}

H - 冰！- CodeForces - 740D

题目链接

题意

给出一棵树和点权边权，一个点能控制另一个点的条件是：

被控制点在控制点的子树上
控制点到被控制点的边权之和小于等于被控制点的点权

问每个点能控制的点个数

思路

一开始的思路是，建立带权有向图

满足第一个条件，可以用 dfs 遍历，如果从一个点能遍历到另一个说明另一个点在该点的子树上

满足第二个条件，主要问题是计算控制点到被控制点的边权，考虑到如果一个一个加肯定会爆，所以先计算出所有点到根结点 1 的路径边权（用 Dijkstra 的堆优化做），再用被控制点到根结点的边权减去控制点到根结点的边权就得到两点的路径边权

（说了这么多还是TLE了…

查了一下题解，倍增 + 树上差分 + dfs
对代码加了点注释，还没能完全搞清楚

代码

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N = 200010;

LL a; // 顶点个数
LL s1[N]; // 顶点权重
LL head[N]; // 存储i点的第一个子结点（和fa[i][0]互为逆运算）
LL top;
LL fa[N][20]; // fa[i][j] 表示i结点的第2^j个祖先结点
LL dis[N], x, y, z;
LL ans[N]; // 差分数组 后面变成i能控制的点的个数
struct node
{
	LL last, to, dis; // last：父结点的head || to：子结点 || dis：边权
} s[N]; // DFS数组

void add(LL l1, LL l2, LL l3)
{
    top ++ ;
	s[top].last = head[l1];
	s[top].to = l2;
	s[top].dis = l3;
	head[l1] = top;
}
void dfs(LL n)
{
	LL now = n;
	for (LL i = 1; i <= 19; i ++ )
        fa[n][i] = fa[fa[n][i-1]][i-1]; // 维护倍增数组
	for (LL i = 19; i >= 0; i -- )
    {
		if(fa[now][i] && dis[n] - dis[fa[now][i]] <= s1[n])
            now = fa[now][i]; // 寻找第一个不满足条件的祖宗（的父结点就是满足条件的
	}
    // 差分
	ans[fa[now][0]] -- ;
	ans[fa[n][0]] ++ ;
    // DFS
	for (LL i = head[n]; i; i = s[i].last )
    {
		dis[s[i].to] = dis[n] + s[i].dis;
		dfs(s[i].to);
		ans[n] += ans[s[i].to]; // 维护答案
	}
}
int main()
{
	scanf("%lld", &a);
	for (LL i = 1; i <= a; i ++ ) scanf("%lld", &s1[i]);
	for (LL i = 2; i <= a; i ++ )
    {
		scanf("%lld%lld", &fa[i][0], &x); // fa[i][0]就是i的父结点
		add(fa[i][0], i, x);
	}
	dfs(1);
	for (LL i = 1; i <= a; i ++ ) printf("%lld ", ans[i]);
	return 0;
}