作业部分
区间选点 II
题意
给定一个数轴上的 n 个区间，要求在数轴上选取最少的点使得第 i 个区间 [ai, bi] 里至少有 ci 个点
输入
5
3 7 3
8 10 3
6 8 1
1 3 1
10 11 1
输出
6
思路
这道题的简单思路和更好的方法当然是贪心，容易想清楚还速度快。但是这次的作业主要考察使用差分约束。在使用差分约束的时候，跑最短路求的是最大值，但是这道题要求的是求最小的答案，所以要跑一个最长路，为什么会这样呢？像是这道题，题意给出的约束有
，这个可以转换为
（如果在找最大值的时候要变成小于号形式）
还有一个隐含条件
这个式子也化成大于号形式，再在数轴上模拟一下，你会发现在大于号形式的求最长路的过程就是求最小的区间点的过程，当然，求最长路的过程使用SPFA。
总结
这道题使用了差分约束系统和SPFA。
AC代码
#include<stdio.h>
#include<algorithm>
#include<cmath>
#include<queue>
#define inf -99999
using namespace std;
struct edge {
int w, to, nex;
}e[200000];
int tot, head[60000], vis[60000], dis[60000];
void add(int u, int v, int w) {
e[++tot].to = v, e[tot].nex = head[u];
e[tot].w = w, head[u] = tot;
}
void spfa(int s) {
queue<int> q;
for (int i = 0; i < 51000; i++)
dis[i] = inf;
vis[s] = 1;
dis[s] = 0;
q.push(s);
while (!q.empty()) {
int a = q.front();
q.pop();
vis[a] = 0;
int b = head[a];
while (b != 0) {
if (dis[e[b].to] < dis[a] + e[b].w) {
dis[e[b].to] = dis[a] + e[b].w;
if (vis[e[b].to] == 0) {
vis[e[b].to] = 1;
q.push(e[b].to);
}
}
b = e[b].nex;
}
}
}
int main() {
int n;
scanf_s("%d", &n);
int minp = 99999, maxp = -1;
for (int i = 0; i < n; i++) {
int a, b, c;
scanf_s("%d %d %d", &a, &b, &c);
add(a, b + 1, c);
maxp = maxp > (b+1) ? maxp : (b + 1);
minp = minp < a ? minp : a ;
}
for (int i = minp; i <= maxp; i++) {
add(i - 1, i, 0);
add(i, i - 1, -1);
}
spfa(minp);
printf("%d", dis[maxp]);
}
猫猫向前冲
众所周知， TT 是一位重度爱猫人士，他有一只神奇的魔法猫。
有一天，TT 在 B 站上观看猫猫的比赛。一共有 N 只猫猫，编号依次为1，2，3，…，N进行比赛。比赛结束后，Up 主会为所有的猫猫从前到后依次排名并发放爱吃的小鱼干。不幸的是，此时 TT 的电子设备遭到了宇宙射线的降智打击，一下子都连不上网了，自然也看不到最后的颁奖典礼。
不幸中的万幸，TT 的魔法猫将每场比赛的结果都记录了下来，现在他想编程序确定字典序最小的名次序列，请你帮帮他。
题意
现在有N只猫在做比赛，请你输出按字典序大小排序的输赢顺序
输入
输入有若干组，每组中的第一行为二个数N（1<=N<=500），M；其中N表示猫猫的个数，M表示接着有M行的输入数据。接下来的M行数据中，每行也有两个整数P1，P2表示即编号为 P1 的猫猫赢了编号为 P2 的猫猫。
4 3
1 2
2 3
4 3
输出
1 2 4 3
思路
这道题就类似于拓补排序，因为像是A和B都赢了C，那当然是先输出A和B再输出C了，所以一开始输入数据的时候，就记录下每个节点的入度，然后第二步，把所有入度是0的点全部压进小根堆，在后面每次弹出一个点，就把与他相连的所有点的入度减一，顺便查看入度是不是0了，如果是的话，那么就进堆，循环上述步骤即可。
总结
这道题主要考察拓补排序。
AC代码
#include<iostream>
#include<queue>
#include<utility>
#include<string.h>
using namespace std;
struct edge{
int v,nex;
}e[60000];
int head[60000], cnt[600], tot;
void add(int u, int v) {
e[++tot].v = v, e[tot].nex = head[u];
head[u] = tot;
}
int main() {
int n;
while (cin>>n) {
tot = 0;
memset(head, 0, sizeof head);
memset(cnt, 0, sizeof cnt);
int m;
scanf("%d", &m);
for (int i = 0; i < m; i++) {
int a, b;
scanf("%d %d", &a, &b);
add(a, b);
cnt[b]++;
}
priority_queue<int> q;
for (int i = 1; i <= n; i++)
if (cnt[i] == 0)
q.push(-i);
int sum = 0;
while (!q.empty()) {
int a = -q.top();
int b = head[a];
q.pop();
sum++;
if (sum != n)
printf("%d ", a);
else
printf("%d", a);
while (b != 0) {
cnt[e[b].v]--;
if (cnt[e[b].v] == 0)
q.push(-e[b].v);
b = e[b].nex;
}
}
printf("\n");
}
}
班长竞选
大学班级选班长，N 个同学均可以发表意见 若意见为 A B 则表示 A 认为 B 合适，意见具有传递性，即 A 认为 B 合适，B 认为 C 合适，则 A 也认为 C 合适 勤劳的 TT 收集了M条意见，想要知道最高票数，并给出一份候选人名单，即所有得票最多的同学，你能帮帮他吗？
题意
现在有N个点，每个点的人都能给其他点的人投票，而且这个投票具有传递性，也就是A给B投票，B给C投票的话，那么C就有2票，现在要求求出得票最多的那些人。
输入
本题有多组数据。第一行 T 表示数据组数。每组数据开始有两个整数 N 和 M (2 <= n <= 5000, 0 <m <= 30000)，接下来有 M 行包含两个整数 A 和 B(A != B) 表示 A 认为 B 合适。
2
4 3
3 2
2 0
2 1
3 3
1 0
2 1
0 2
输出
对于每组数据，第一行输出 “Case x: ”，x 表示数据的编号，从1开始，紧跟着是最高的票数。 接下来一行输出得票最多的同学的编号，用空格隔开，不忽略行末空格！
Case 1: 2
0 1
Case 2: 2
0 1 2
思路
我最初想到的是用Floyed算法，这种方法很直接，因为我看到题目中要求的时间是2s，这么长的时间，可能我优化一下，Floyed就卡过去了呢，结果没想到优化了几遍都是超时，只能老老实实用SCC连通分量的方法来求解。先用kosaraju算法来求出每个连通分量，求得过程中顺便求出每个SCC的价值，这时候就能缩点，反正每个SCC的价值都已经知道了。缩点就把这些点缩在一起，编号是kosaraju算法中第二遍dfs时给的编号scnt，然后就是求价值，我用递归的方法，假设有一条边是A>B>C，那么就递归到A，把他们的价值全都给加起来，注意，上面求价值的集合只有出度是0的集合，然后把这些集合的价值和编号都压进一个set中，只输出最大价值的点，因为这些点还要按照字典排序，所以我把他们都压进一个小根堆，然后再输出即可。
总结
这道题考察SCC连通分量的使用。
AC代码
#include<stdio.h>
#include<vector>
#include<string.h>
#include<queue>
#include<set>
using namespace std;
vector<int> G[6000], G1[6000], G2[6000], q;
int c[6000], cnt[6000], dcnt, scnt, vis[6000], dfn[6000], sum, VIS[6000];
bool is[6000];
struct par {
int u, w;
bool operator <(const par& p) const {
if (w != p.w) return w > p.w;
return u < p.u;
}
};
set<par> m;
void cal(int u) {
sum += cnt[u];
VIS[u] = true;
for (int i = 0; i < G2[u].size(); i++)
if(!VIS[G2[u][i]])
cal(G2[u][i]);
}
void dfs(int x) {
vis[x] = 1;
for (int i = 0; i < G[x].size(); i++)
if (!vis[G[x][i]]) dfs(G[x][i]);
dfn[++dcnt] = x;
}
void dfs2(int x) {
cnt[scnt]++;
c[x] = scnt;
for (int i = 0; i < G1[x].size(); i++)
if (!c[G1[x][i]]) dfs2(G1[x][i]);
}
void kosaraju(int n) {
dcnt = scnt = 0;
memset(c, 0, sizeof c);
memset(vis, 0, sizeof vis);
for (int i = 1; i < n; i++)
if (!vis[i]) dfs(i);
for (int i = n; i >= 1; i--)
if (!c[dfn[i]]) ++scnt, dfs2(dfn[i]);
}
int main() {
int N;
scanf("%d", &N);
for (int i = 1; i <= N; i++) {
int N, M;
scanf("%d %d", &N, &M);
for (int j = 0; j < M; j++) {
int a, b;
scanf("%d %d", &a, &b);
G[a].push_back(b);
G1[b].push_back(a);
}
kosaraju(N);
//开始缩点
for(int x=0;x<N;x++)
for (int j = 0; j < G[x].size(); j++) {
if (c[x] == c[G[x][j]])continue;
G2[c[G[x][j]]].push_back(c[x]);
is[c[x]] = true;
}
for (int j = 1; j <= scnt; j++)
if (!is[j]) q.push_back(j);//这些是入度是 0的SCC
int max = 0;
for (int j = 0; j < q.size(); j++) {
int u = q[j];
sum = 0;
cal(u);//用这个函数计算sum
for (int i = 0; i <= scnt; i++)
VIS[i] = false;
sum--;
if (sum > max)
max = sum;
m.insert(par{ u,sum });
}
q.clear();
printf("Case %d: %d\n", i,m.begin()->w);
int now = 0;
set<par>::iterator it = m.begin();
priority_queue<int> pri;
while (it != m.end())
{
now = it->u;
int cc = 0;
if (it->w != max)
break;
for (int h = 0; h < N; h++)
if (c[h] == now)
pri.push(-h);
/*{ if (cc == 0) {
cc++;
printf("%d", h);
}
else
printf(" %d", h);
}*/
it++;
}
printf("%d", -pri.top());
pri.pop();
while (pri.size()) {
printf(" %d", -pri.top());
pri.pop();
}
printf("\n");
for (int i = 0; i < N; i++) {
G[i].clear();
G1[i].clear();
}
for (int i = 0; i <= scnt; i++) {
cnt[i] = 0;
G2[i].clear();
is[i] = false;
}
m.clear();
}
}
考试部分
HRZ 的序列
相较于咕咕东，瑞神是个起早贪黑的好孩子，今天早上瑞神起得很早，刷B站时看到了一个序列 ，他对 这个序列产生了浓厚的兴趣，他好奇是否存在一个数 ，使得一些数加上 ，一些数减去 ，一些数不 变，使得整个序列中所有的数相等，其中对于序列中的每个位置上的数字，至多只能执行一次加运算或 减运算或是对该位置不进行任何操作。由于瑞神只会刷B站，所以他把这个问题交给了你
题意
简单说，就是有一组数字，然后他们有些数字加上一个数字，有些数字减去这个数字，有些数字能保持不变，然后这个序列的最终所有数字相等。
思路
一开始用了二分答案，唉，一开始想到可能和最近写过的作业有关就这么写了，就是用最大值减去最小值，然后用0到这个值来二分试出结果，然后直到我调bug一小时并交了以后，才想到要是用set来装里面的元素，要是只有1或者两个元素的话，就直接过了，要是有3个元素的话，判断3个元素之间的间隔，要是间隔一样的话那就过了，要是元素大于3个的话，说明这个序列有问题就输出NO。
输入
输入第一行是一个正整数 表示数据组数。 接下来对于每组数据，输入的第一个正整数 表示序列 的长 度，随后一行有 个整数，表示序列 。
2
5
1 2 3 4
5
5 1 2 3 4 5
输出
输出共包含 行，每组数据输出一行。对于每组数据，如果存在这样的K，输出"YES"，否则输出“NO”。 （输出不包含引号）
NO
NO
总结
能正确想明白这道题中数字只有小于等于3个的时候才可能YES是关键
AC代码
#include<stdio.h>
#include<set>
using namespace std;
int main() {
int t;
scanf_s("%d", &t);
for (int i = 0; i < t; i++) {
int n;
set<long long> sim;
scanf_s("%d", &n);
for (int i = 0; i < n; i++) {
long long a;
scanf_s("%lld", &a);
if(sim.size()<=4)
sim.insert(a);
}
if (sim.size() > 3) {
printf("NO\n");
}
else if (sim.size() == 3) {
long long a, b, c;
set<long long>::iterator m = sim.begin();
a = *m;
b = *(++m);
c = *(++m);
if ((b - a) != (c - b)) printf("NO\n");
else printf("YES\n");
}
else {
printf("YES\n");
}
sim.clear();
}
}
| HRZ 学英语 |
瑞神今年大三了，他在寒假学会了英文的26个字母，所以他很兴奋！于是他让他的朋友TT考考他，TT想 到了一个考瑞神的好问题：给定一个字符串，从里面寻找连续的26个大写字母并输出！但是转念一想， 这样太便宜瑞神了，所以他加大了难度：现在给定一个字符串，字符串中包括26个大写字母和特殊字 符'?'，特殊字符'？'可以代表任何一个大写字母。现在TT问你是否存在一个位置连续的且由26个大写字 母组成的子串，在这个子串中每个字母出现且仅出现一次，如果存在，请输出从左侧算起的第一个出现 的符合要求的子串，并且要求，如果有多组解同时符合位置最靠左，则输出字典序最小的那个解！如果 不存在，输出-1！ 这下HRZ蒙圈了，他刚学会26个字母，这对他来说太难了，所以他来求助你，请你帮 他解决这个问题，报酬是可以帮你打守望先锋。
说明：字典序 先按照第一个字母，以 A、B、C……Z 的顺序排列；如果第一个字母一样，那么比较第二 个、第三个乃至后面的字母。如果比到最后两个单词不一样长（比如，SIGH 和 SIGHT），那么把短者排 在前。例如
上面两种填法，都可以构成26个字母，但是我们要求字典序最小，只能取前者。
注意，题目要求的是 第一个出现的，字典序最小的
题意
就是给出一大串字符串，然后要求你在里面找有没有连续的一段包含26个字母子字符串并输出
输入
输入只有一行，一个符合题目描述的字符串。
ABC??FGHIJK???OPQR?TUVWXY?
输出
输出只有一行，如果存在这样的子串，请输出，否则输出-1
ABCDEFGHIJKLMNOPQRSTUVWXYZ
思路
因为要求的是一段连续的序列，那只能一段一段来判断是不是，那就只能使用滑窗来做，一开始从字符串中截取26个字符，然后每次向右滑动一格，顺便对map中存储的这个子字符串的数量做统计，如果都是1的话那就成功，如果缺少的字符等于？的数量的话，也成功。这次考试这道题我本来能满分的，结果因为我在滑窗的时候，忘了移动左坐标，导致才过了3个点。
总结
这道题考察滑窗算法
AC代码
#include<iostream>
#include<map>
#include<string.h>
using namespace std;
map<char, int> th;
string str;
int beg = 0, nbeg = 25;
bool check() {
map<char, int>::iterator it = th.begin();
it++;
int req = 0;
while (it != th.end()) {
if (it->second != 1)
req++;//记录缺少的量
it++;
}
if (th['?'] != req) return false;
it = th.begin();
for (int i = beg; i <= nbeg; i++) {
if (str[i] == '?') {
while (it != th.end()) {
if (it->second == 0) {
printf("%c", it->first);
it++;
break;
}
it++;
}
}
else
printf("%c", str[i]);
}
return true;
}
int main() {
cin >> str;
int end = str.size();
if (end < 26) {
printf("-1");
return 0;
}
char fo = 'A';
for (int i = 0; i < 26; i++) th[fo + i] = 0;
th['?'] = 0;
for (int i = 0; i < 26; i++)
th[str[i]]++;
while (nbeg < end) {
if (check()) {
return 0;
}
th[str[beg]]--;
beg++;
nbeg++;
if (nbeg != end)
th[str[nbeg]]++;
}
printf("-1");
}
| 咕咕东的奇妙序列 |
咕咕东 正在上可怕的复变函数，但对于稳拿A Plus的 咕咕东 来说，她早已不再听课，此时她在睡梦中 突然想到了一个奇怪的无限序列：112123123412345 ......这个序列由连续正整数组成的若干部分构成，其 中第一部分包含1至1之间的所有数字，第二部分包含1至2之间的所有数字，第三部分包含1至3之间的所 有数字，第i部分总是包含1至i之间的所有数字。所以，这个序列的前56项会是 11212312341234512345612345671234567812345678912345678910，其中第1项是1，第3项是2，第20项是 5，第38项是2，第56项是0。咕咕东 现在想知道第 k 项数字是多少！但是她睡醒之后发现老师讲的东西 已经听不懂了，因此她把这个任务交给了你。
题意
题目说清楚了，不再简述。
输入
输入由多行组成。
第一行一个整数q表示有q组询问
接下来第i+1行表示第i个输入 ，表示询问第 项数字。
5
1
3
20
38
56
输出
1
2
5
2
0
思路
这么大的数据量，当然只能把指定要询问的数字给缩小了，我先求出1位数到9位数，所有同位数的数字的序列和，这是1号数组，还有每个多位数的最大数字的序列是多少位，这是二号数组，然后就用指定的数字和一号数组的数字做比较，得出他是多少位的，减去他的少一位数字的相加和，这个数据在1号数组中，然后就能得到只有本位数字的相加和，然后用二分查找的方法，找到最后比他小的那个本位数字，条件是那个数字的序列和比他小，这个数字加一以后的数字产生的序列和比指定的数字大。然后把这个求出的数字的序列和给减去，就能得到只有一位数字产生的序列和，然后此时的这个数字和2号数组比较，就能得到产生这个数字的最后数字是多少位的，再次使用二分，找到产生这个序列的最后数字，将他的序列和给减去，剩下的数据就是所求数字的第几位，这个就是答案。
总结
这道题，考察数学？
AC代码
#include<iostream>
using namespace std;
long long a[20], b[20];//a用来装多少位数能到哪里，b用来装每一位数的最后一位能累计到几位
bool check(long long mid, long long sig, long long inq) {
long long l = b[sig - 1] + sig, r = l + (mid - 1) * sig;
return (l + r) * mid / 2 < inq;
}
int main() {
long long k = 9, l = 0, r = 0;
for (long long i = 1; i <= 9; i++) {
l = r + i, r = l + (k - 1) * i;
a[i] = a[i - 1] + (l + r) * k / 2;
k *= 10;
}
k = 9;
for (long long i = 1; i <= 9; i++) {
b[i] = b[i - 1] + k * i;
k *= 10;
}
int q;
scanf("%d", &q);
long long inq;
for (int i = 0; i < q; i++) {
scanf("%lld", &inq);
int sig = 0;
for(int j=1;j<=9;j++)
if (a[j] >= inq) {
sig = j;
break;
}
inq -= a[sig - 1];//找到这个数字是几位数,sig就代表，减去之后，剩下的就是
//单纯的由这个位数数字所生成的
//下一步，找出是这个位数的哪个数字生成的
l = 0, r = 1e9;
while (l < r) {
long long mid = (l + r) >> 1;
if (check(mid, sig, inq)) l = mid + 1;
else r = mid ;
}
l = b[sig - 1] + sig;
long long c = l + (r - 2) * sig;
inq -= (l + c) * (r - 1) / 2;
long long now = 0;
for(int i=1;i<=9;i++)
if (b[i] >= inq) {
now = i;
break;
}//这一步知道了这个剩余的数是由几位数产生的
l = 0, r = 1e9;
int k = 0;
if (now == 1)
k = 0;
else {
k = 9;
for (int i = 0; i < now - 2; i++)
k = k * 10 + 9;
}
while (l < r) {//寻找是哪个数字产生的
long long mid = (l + r) >> 1;
if ((b[now - 1] + (mid-k) * now) < inq) l = mid + 1;
else r = mid;//r就是产生inq的数字
}
inq -= (b[now - 1] + (r - 1 - k) * now);//inq是r的第inq个数
if (now == 1) {
printf("%lld\n", r);
}
else if(now == inq)
printf("%lld\n", r % 10);
else {
now = now - inq;
long long sur = 0;
for (int i = 0; i < now; i++) {
r = r / 10;
sur = r % 10;
}
printf("%lld\n", sur);
}
}
}
