这几天比赛比较多，没有来得及写，索性今天一并补上了。
Day6 打了一场比赛。
H题
H - How to do that
Okabe and Super Hacker Daru are stacking and removing boxes. There are n boxes numbered from 1 to n. Initially there are no boxes on the stack.
Okabe, being a control freak, gives Daru 2n commands: n of which are to add a box to the top of the stack, and n of which are to remove a box from the top of the stack and throw it in the trash. Okabe wants Daru to throw away the boxes in the order from 1 to n. Of course, this means that it might be impossible for Daru to perform some of Okabe's remove commands, because the required box is not on the top of the stack.
That's why Daru can decide to wait until Okabe looks away and then reorder the boxes in the stack in any way he wants. He can do it at any point of time between Okabe's commands, but he can't add or remove boxes while he does it.
Tell Daru the minimum number of times he needs to reorder the boxes so that he can successfully complete all of Okabe's commands. It is guaranteed that every box is added before it is required to be removed.
Input
The first line of input contains the integer n (1 ≤ n ≤ 3·105) — the number of boxes.
Each of the next 2n lines of input starts with a string "add" or "remove". If the line starts with the "add", an integer x (1 ≤ x ≤ n) follows, indicating that Daru should add the box with number x to the top of the stack.
It is guaranteed that exactly n lines contain "add" operations, all the boxes added are distinct, and n lines contain "remove" operations. It is also guaranteed that a box is always added before it is required to be removed.
Output
Print the minimum number of times Daru needs to reorder the boxes to successfully complete all of Okabe's commands.
Examples
Input
3
add 1
remove
add 2
add 3
remove
remove Output
1 Input
7
add 3
add 2
add 1
remove
add 4
remove
remove
remove
add 6
add 7
add 5
remove
remove
remove Output
2 Note
In the first sample, Daru should reorder the boxes after adding box 3 to the stack.
In the second sample, Daru should reorder the boxes after adding box 4 and box 7 to the stack.
解释：贪心咯，每次remove的时候不相等就排序一定是最优的鸭，但是暴力会T的吧，毕竟排序的次数有点多，可以用优先队列来优化
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<queue>
#include<stack>
using namespace std;
priority_queue<int, vector<int>, greater<int> >q;
int x,n,ans,si;
string s;
int f;
int main()
{
scanf("%d",&n);
f = 0;
ans = 0;
for(int i = 0;i < 2 * n; ++i)
{
cin>>s;
if(s[0] == 'a')
{
scanf("%d",&x);
if(!q.empty() && q.top() < x) f = q.size() + 1;
q.push(x);
}
else
{
if(f == q.size())
{
ans++;
f = 0;
}
q.pop();
}
}
printf("%d\n",ans);
return 0;
} Jzzhu is the president of country A. There are n cities numbered from 1 to n in his country. City 1 is the capital of A. Also there are m roads connecting the cities. One can go from city ui to vi (and vise versa) using the i-th road, the length of this road is xi. Finally, there are k train routes in the country. One can use the i-th train route to go from capital of the country to city si (and vise versa), the length of this route is yi.
Jzzhu doesn't want to waste the money of the country, so he is going to close some of the train routes. Please tell Jzzhu the maximum number of the train routes which can be closed under the following condition: the length of the shortest path from every city to the capital mustn't change.
Input
The first line contains three integers n, m, k (2 ≤ n ≤ 105; 1 ≤ m ≤ 3·105; 1 ≤ k ≤ 105).
Each of the next m lines contains three integers ui, vi, xi (1 ≤ ui, vi ≤ n; ui ≠ vi; 1 ≤ xi ≤ 109).
Each of the next k lines contains two integers si and yi (2 ≤ si ≤ n; 1 ≤ yi ≤ 109).
It is guaranteed that there is at least one way from every city to the capital. Note, that there can be multiple roads between two cities. Also, there can be multiple routes going to the same city from the capital.
Output
Output a single integer representing the maximum number of the train routes which can be closed.
Examples
Input
5 5 3
1 2 1
2 3 2
1 3 3
3 4 4
1 5 5
3 5
4 5
5 5 Output
2 Input
2 2 3
1 2 2
2 1 3
2 1
2 2
2 3 Output
2
解释:
比赛时想的是给铁路做标记，然后跑最短路的时候尽量选没被标记的边，最后统计不在最短路里的铁路就是可以删除的。
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<queue>
#include<stack>
using namespace std;
const int N = 800010;
struct node
{
int u,v,w,next;
}t[N];
int head[N],dis[N],d[N],a[N],b[N];
bool vis[N];
int n,m,k,ans,tot,sum;
void add(int u,int v,int w)
{
t[++tot].u = u;
t[tot].v = v;
t[tot].w = w;
t[tot].next = head[u];
head[u] = tot;
}
void spfa(int st)
{
deque<int>q;
q.push_back(st);
dis[st] = 0;
vis[st] = 1;
sum = 0;
tot = 1;
while(!q.empty())
{
int u = q.front();
q.pop_front();
tot--;
sum -= dis[u];
vis[u] = 0;
for(int i = head[u];i != -1;i = t[i].next)
{
if(dis[t[i].v] > dis[u] + t[i].w)
{
d[t[i].v] = 1;
dis[t[i].v] = dis[u] + t[i].w;
if(!vis[t[i].v])
{
vis[t[i].v] = 1;
if(!q.empty() && (dis[t[i].v] * tot > sum || dis[q.front()] < dis[t[i].v]))
q.push_back(t[i].v);
else q.push_front(t[i].v);
tot++;
sum += dis[t[i].v];
}
}
else if(dis[t[i].v] == dis[u] + t[i].w) d[t[i].v]++;
}
}
}
int main()
{
scanf("%d%d%d",&n,&m,&k);
memset(head,-1,sizeof(head));
memset(dis,0x3f,sizeof(dis));
memset(vis,0,sizeof(vis));
for(int i = 0;i < m; ++i)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
add(y,x,z);
}
for(int i = 0;i < k; ++i)
{
scanf("%d%d",&a[i],&b[i]);
add(1,a[i],b[i]);
add(a[i],1,b[i]);
}
spfa(1);
ans = 0;
for(int i = 0;i < k; ++i)
{
if(dis[a[i]] < b[i]) ans++;
if(dis[a[i]] == b[i])
if(d[a[i]] > 1)
{
ans++;
d[a[i]]--;
}
}
printf("%d\n",ans);
return 0;
}
F题
http://codeforces.com/problemset/problem/849/C
这个题主要是读题的功夫，构造一个字符串
只由1个字母可以组合出1+2+3+...+n的代价，那么对于k来说，就可以每次都找最大的s满足s = 1+2+3+...+n1,然后换个字母让剩下的部分再重复这个操作就可以了
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 100001;
long long f[N];
int n;
int main()
{
f[1] = 1;
for(int i = 2;i <= N; ++i)
f[i] = f[i - 1] + i;
char ch = 'a';
scanf("%d",&n);
if(!n) printf("a\n");
while(n)
{
int p = lower_bound(f + 1,f + N,n) - f;
if(f[p] == n)
{
for(int i = 0;i <= p; ++i) printf("%c",ch);
n = 0;
}
else
{
p--;
n -= f[p];
for(int i = 0;i <= p; ++i) printf("%c",ch);
ch++;
}
}
printf("\n");
return 0;
}
Day7 上海大学的比赛，就签了个到再也不会了嘤嘤嘤
补了一个找规律的数学题，就不发了
CSL的字符串
链接：https://ac.nowcoder.com/acm/contest/551/D
来源：牛客网
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 524288K，其他语言1048576K
64bit IO Format: %lld
题目描述
CSL 以前不会字符串算法，经过一年的训练，他还是不会……于是他打算向你求助。
给定一个字符串，只含有可打印字符，通过删除若干字符得到新字符串，新字符串必须满足两个条件：
- 原字符串中出现的字符，新字符串也必须包含。
- 新字符串中所有的字符均不相同。
- 新字符串的字典序是满足上面两个条件的最小的字符串。
输入描述:
仅一行，有一个只含有可打印字符的字符串 s。
|s|≤10^5
输出描述:
在一行输出字典序最小的新字符串。
示例1
输入
bab
输出
ab
示例2
输入
baca
输出
bac
备注:
ASCII字符集包含 94 个可打印字符(0x21 - 0x7E)，不包含空格。
比赛时怎么也想不出哪里错了，实在找不出特殊样例（现在也一样没找出来），就直接看题解吧。
对于字符串s，我们求出其每个字符最后出现的位置，用栈遍历s，对于第i个字符，如果栈顶字符大于这个字符并且栈顶字符最后出现的位置大于i就弹出栈顶字符并存入第i个字符，否则直接存入第i个字符，最后倒序输出栈内字符。
Day8 学了一点tarjan算法，做了几个模板题，再加上补前几次比赛的题，挺充实的嘤嘤嘤
京公网安备 11010502036488号