作業(yè)部分
區(qū)間選點 II
題意
給定一個數(shù)軸上的 n 個區(qū)間，要求在數(shù)軸上選取最少的點使得第 i 個區(qū)間 [ai, bi] 里至少有 ci 個點
輸入
5
3 7 3
8 10 3
6 8 1
1 3 1
10 11 1
輸出
6
思路
這道題的簡單思路和更好的方法當然是貪心，容易想清楚還速度快。但是這次的作業(yè)主要考察使用差分約束。在使用差分約束的時候，跑最短路求的是最大值，但是這道題要求的是求最小的答案，所以要跑一個最長路，為什么會這樣呢？像是這道題，題意給出的約束有
，這個可以轉(zhuǎn)換為
（如果在找最大值的時候要變成小于號形式）
還有一個隱含條件
這個式子也化成大于號形式，再在數(shù)軸上模擬一下，你會發(fā)現(xiàn)在大于號形式的求最長路的過程就是求最小的區(qū)間點的過程，當然，求最長路的過程使用SPFA。
總結(jié)
這道題使用了差分約束系統(tǒng)和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進行比賽。比賽結(jié)束后，Up 主會為所有的貓貓從前到后依次排名并發(fā)放愛吃的小魚干。不幸的是，此時 TT 的電子設(shè)備遭到了宇宙射線的降智打擊，一下子都連不上網(wǎng)了，自然也看不到最后的頒獎典禮。
不幸中的萬幸，TT 的魔法貓將每場比賽的結(jié)果都記錄了下來，現(xiàn)在他想編程序確定字典序最小的名次序列，請你幫幫他。
題意
現(xiàn)在有N只貓在做比賽，請你輸出按字典序大小排序的輸贏順序
輸入
輸入有若干組，每組中的第一行為二個數(shù)N（1<=N<=500），M；其中N表示貓貓的個數(shù)，M表示接著有M行的輸入數(shù)據(jù)。接下來的M行數(shù)據(jù)中，每行也有兩個整數(shù)P1，P2表示即編號為 P1 的貓貓贏了編號為 P2 的貓貓。
4 3
1 2
2 3
4 3
輸出
1 2 4 3
思路
這道題就類似于拓補排序，因為像是A和B都贏了C，那當然是先輸出A和B再輸出C了，所以一開始輸入數(shù)據(jù)的時候，就記錄下每個節(jié)點的入度，然后第二步，把所有入度是0的點全部壓進小根堆，在后面每次彈出一個點，就把與他相連的所有點的入度減一，順便查看入度是不是0了，如果是的話，那么就進堆，循環(huán)上述步驟即可。
總結(jié)
這道題主要考察拓補排序。
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 個同學均可以發(fā)表意見 若意見為 A B 則表示 A 認為 B 合適，意見具有傳遞性，即 A 認為 B 合適，B 認為 C 合適，則 A 也認為 C 合適 勤勞的 TT 收集了M條意見，想要知道最高票數(shù)，并給出一份候選人名單，即所有得票最多的同學，你能幫幫他嗎？
題意
現(xiàn)在有N個點，每個點的人都能給其他點的人投票，而且這個投票具有傳遞性，也就是A給B投票，B給C投票的話，那么C就有2票，現(xiàn)在要求求出得票最多的那些人。
輸入
本題有多組數(shù)據(jù)。第一行 T 表示數(shù)據(jù)組數(shù)。每組數(shù)據(jù)開始有兩個整數(shù) N 和 M (2 <= n <= 5000, 0 <m <= 30000)，接下來有 M 行包含兩個整數(shù) A 和 B(A != B) 表示 A 認為 B 合適。
2
4 3
3 2
2 0
2 1
3 3
1 0
2 1
0 2
輸出
對于每組數(shù)據(jù)，第一行輸出 “Case x: ”，x 表示數(shù)據(jù)的編號，從1開始，緊跟著是最高的票數(shù)。 接下來一行輸出得票最多的同學的編號，用空格隔開，不忽略行末空格！
Case 1: 2
0 1
Case 2: 2
0 1 2
思路
我最初想到的是用Floyed算法，這種方法很直接，因為我看到題目中要求的時間是2s，這么長的時間，可能我優(yōu)化一下，F(xiàn)loyed就卡過去了呢，結(jié)果沒想到優(yōu)化了幾遍都是超時，只能老老實實用SCC連通分量的方法來求解。先用kosaraju算法來求出每個連通分量，求得過程中順便求出每個SCC的價值，這時候就能縮點，反正每個SCC的價值都已經(jīng)知道了?？s點就把這些點縮在一起，編號是kosaraju算法中第二遍dfs時給的編號scnt，然后就是求價值，我用遞歸的方法，假設(shè)有一條邊是A>B>C，那么就遞歸到A，把他們的價值全都給加起來，注意，上面求價值的集合只有出度是0的集合，然后把這些集合的價值和編號都壓進一個set中，只輸出最大價值的點，因為這些點還要按照字典排序，所以我把他們都壓進一個小根堆，然后再輸出即可。
總結(jié)
這道題考察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);//用這個函數(shù)計算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站時看到了一個序列 ，他對 這個序列產(chǎn)生了濃厚的興趣，他好奇是否存在一個數(shù) ，使得一些數(shù)加上 ，一些數(shù)減去 ，一些數(shù)不 變，使得整個序列中所有的數(shù)相等，其中對于序列中的每個位置上的數(shù)字，至多只能執(zhí)行一次加運算或 減運算或是對該位置不進行任何操作。由于瑞神只會刷B站，所以他把這個問題交給了你
題意
簡單說，就是有一組數(shù)字，然后他們有些數(shù)字加上一個數(shù)字，有些數(shù)字減去這個數(shù)字，有些數(shù)字能保持不變，然后這個序列的最終所有數(shù)字相等。
思路
一開始用了二分答案，唉，一開始想到可能和最近寫過的作業(yè)有關(guān)就這么寫了，就是用最大值減去最小值，然后用0到這個值來二分試出結(jié)果，然后直到我調(diào)bug一小時并交了以后，才想到要是用set來裝里面的元素，要是只有1或者兩個元素的話，就直接過了，要是有3個元素的話，判斷3個元素之間的間隔，要是間隔一樣的話那就過了，要是元素大于3個的話，說明這個序列有問題就輸出NO。
輸入
輸入第一行是一個正整數(shù) 表示數(shù)據(jù)組數(shù)。 接下來對于每組數(shù)據(jù)，輸入的第一個正整數(shù) 表示序列 的長 度，隨后一行有 個整數(shù)，表示序列 。
2
5
1 2 3 4
5
5 1 2 3 4 5
輸出
輸出共包含 行，每組數(shù)據(jù)輸出一行。對于每組數(shù)據(jù)，如果存在這樣的K，輸出"YES"，否則輸出“NO”。 （輸出不包含引號）
NO
NO
總結(jié)
能正確想明白這道題中數(shù)字只有小于等于3個的時候才可能YES是關(guān)鍵
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想 到了一個考瑞神的好問題：給定一個字符串，從里面尋找連續(xù)的26個大寫字母并輸出！但是轉(zhuǎn)念一想， 這樣太便宜瑞神了，所以他加大了難度：現(xiàn)在給定一個字符串，字符串中包括26個大寫字母和特殊字 符'?'，特殊字符'？'可以代表任何一個大寫字母。現(xiàn)在TT問你是否存在一個位置連續(xù)的且由26個大寫字 母組成的子串，在這個子串中每個字母出現(xiàn)且僅出現(xiàn)一次，如果存在，請輸出從左側(cè)算起的第一個出現(xiàn) 的符合要求的子串，并且要求，如果有多組解同時符合位置最靠左，則輸出字典序最小的那個解！如果 不存在，輸出-1！ 這下HRZ蒙圈了，他剛學會26個字母，這對他來說太難了，所以他來求助你，請你幫 他解決這個問題，報酬是可以幫你打守望先鋒。
說明：字典序 先按照第一個字母，以 A、B、C……Z 的順序排列；如果第一個字母一樣，那么比較第二 個、第三個乃至后面的字母。如果比到最后兩個單詞不一樣長（比如，SIGH 和 SIGHT），那么把短者排 在前。例如
上面兩種填法，都可以構(gòu)成26個字母，但是我們要求字典序最小，只能取前者。
注意，題目要求的是 第一個出現(xiàn)的，字典序最小的
題意
就是給出一大串字符串，然后要求你在里面找有沒有連續(xù)的一段包含26個字母子字符串并輸出
輸入
輸入只有一行，一個符合題目描述的字符串。
ABC??FGHIJK???OPQR?TUVWXY?
輸出
輸出只有一行，如果存在這樣的子串，請輸出，否則輸出-1
ABCDEFGHIJKLMNOPQRSTUVWXYZ
思路
因為要求的是一段連續(xù)的序列，那只能一段一段來判斷是不是，那就只能使用滑窗來做，一開始從字符串中截取26個字符，然后每次向右滑動一格，順便對map中存儲的這個子字符串的數(shù)量做統(tǒng)計，如果都是1的話那就成功，如果缺少的字符等于？的數(shù)量的話，也成功。這次考試這道題我本來能滿分的，結(jié)果因為我在滑窗的時候，忘了移動左坐標，導致才過了3個點。
總結(jié)
這道題考察滑窗算法
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");
}
| 咕咕東的奇妙序列 |
咕咕東 正在上可怕的復變函數(shù)，但對于穩(wěn)拿A Plus的 咕咕東 來說，她早已不再聽課，此時她在睡夢中 突然想到了一個奇怪的無限序列：112123123412345 ......這個序列由連續(xù)正整數(shù)組成的若干部分構(gòu)成，其 中第一部分包含1至1之間的所有數(shù)字，第二部分包含1至2之間的所有數(shù)字，第三部分包含1至3之間的所 有數(shù)字，第i部分總是包含1至i之間的所有數(shù)字。所以，這個序列的前56項會是 11212312341234512345612345671234567812345678912345678910，其中第1項是1，第3項是2，第20項是 5，第38項是2，第56項是0。咕咕東 現(xiàn)在想知道第 k 項數(shù)字是多少！但是她睡醒之后發(fā)現(xiàn)老師講的東西 已經(jīng)聽不懂了，因此她把這個任務(wù)交給了你。
題意
題目說清楚了，不再簡述。
輸入
輸入由多行組成。
第一行一個整數(shù)q表示有q組詢問
接下來第i+1行表示第i個輸入 ，表示詢問第 項數(shù)字。
5
1
3
20
38
56
輸出
1
2
5
2
0
思路
這么大的數(shù)據(jù)量，當然只能把指定要詢問的數(shù)字給縮小了，我先求出1位數(shù)到9位數(shù)，所有同位數(shù)的數(shù)字的序列和，這是1號數(shù)組，還有每個多位數(shù)的最大數(shù)字的序列是多少位，這是二號數(shù)組，然后就用指定的數(shù)字和一號數(shù)組的數(shù)字做比較，得出他是多少位的，減去他的少一位數(shù)字的相加和，這個數(shù)據(jù)在1號數(shù)組中，然后就能得到只有本位數(shù)字的相加和，然后用二分查找的方法，找到最后比他小的那個本位數(shù)字，條件是那個數(shù)字的序列和比他小，這個數(shù)字加一以后的數(shù)字產(chǎn)生的序列和比指定的數(shù)字大。然后把這個求出的數(shù)字的序列和給減去，就能得到只有一位數(shù)字產(chǎn)生的序列和，然后此時的這個數(shù)字和2號數(shù)組比較，就能得到產(chǎn)生這個數(shù)字的最后數(shù)字是多少位的，再次使用二分，找到產(chǎn)生這個序列的最后數(shù)字，將他的序列和給減去，剩下的數(shù)據(jù)就是所求數(shù)字的第幾位，這個就是答案。
總結(jié)
這道題，考察數(shù)學？
AC代碼
#include<iostream>
using namespace std;
long long a[20], b[20];//a用來裝多少位數(shù)能到哪里，b用來裝每一位數(shù)的最后一位能累計到幾位
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];//找到這個數(shù)字是幾位數(shù),sig就代表，減去之后，剩下的就是
//單純的由這個位數(shù)數(shù)字所生成的
//下一步，找出是這個位數(shù)的哪個數(shù)字生成的
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;
}//這一步知道了這個剩余的數(shù)是由幾位數(shù)產(chǎn)生的
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) {//尋找是哪個數(shù)字產(chǎn)生的
long long mid = (l + r) >> 1;
if ((b[now - 1] + (mid-k) * now) < inq) l = mid + 1;
else r = mid;//r就是產(chǎn)生inq的數(shù)字
}
inq -= (b[now - 1] + (r - 1 - k) * now);//inq是r的第inq個數(shù)
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);
}
}
}
