Practice IV
前言
七夕过了，点首悲伤的曲子衬托一下我这只单身狗的悲凉 T^T
另外本篇刷题记又名为“填坑记”
Comma Sprinkler - Kattis - comma
题意
给定句子，要求某个单词如果之前出现逗号，则在句中所有的这个单词之前都要加上逗号，如果之后出现逗号，那么所有这个单词之后都要加上逗号，重复这个过程，直到没有新的逗号加入为止
思路 —— 搜索
填四个月前的坑
本题应该是今年ICPC World Final里面最简单的一道题目
首先对输入进来的单词进行离散化处理，便于起到类似Hash的效果
然后就是搜索了，个人采用了BFS，用dir代表向前打逗号或向后打逗号，再不断更新入队列
另外注意used数组（标记已入过队列的数组）需要开二维，因为可能对于同一个单词可能向前打逗号也可能向后打逗号
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
const int N = 1e6 + 15;
const int inf = 0x3f3f3f3f;
typedef long long ll;
struct Node{
int val, dir;
Node(int pval, int pdir): val(pval), dir(pdir) {}
};
char s[N];
int dot[N];
bool used[N][2];
vector<int> vec[N];
string in[N];
string mp[N];
int pin, pmp;
queue<Node> que;
int getIdx(string& s){
return lower_bound(mp, mp + pmp, s) - mp;
}
void bfs(){
memset(used, false, sizeof(used));
for(int i = 0; i < pin; i++){
if(dot[i] == 1){
que.push(Node(getIdx(in[i]), 1));
que.push(Node(getIdx(in[i + 1]), 0));
used[getIdx(in[i])][1] = true;
used[getIdx(in[i + 1])][0] = true;
}
}
while(!que.empty()){
Node u = que.front();
que.pop();
for(int j = 0; j < vec[u.val].size(); j++){
int k = vec[u.val][j];
if(u.dir == 0 && k != 0 && dot[k - 1] == 0){
dot[k - 1] = 1;
int preval = getIdx(in[k - 1]);
if(used[preval][1] == false){
que.push(Node(preval, 1));
used[preval][1] = true;
}
}else if(u.dir == 1 && k != pin - 1 && dot[k] == 0){
dot[k] = 1;
int sucval = getIdx(in[k + 1]);
if(used[sucval][0] == false){
que.push(Node(sucval, 0));
used[sucval][0] = true;
}
}
}
}
}
int main(){
pin = pmp = 0;
while(~scanf("%s", s)){
int len = strlen(s);
if(s[len - 1] == ',') { dot[pin] = 1; s[len - 1] = 0; }
else if(s[len - 1] == '.') { dot[pin] = 2; s[len - 1] = 0; }
else dot[pin] = 0;
in[pin++] = s;
mp[pmp++] = s;
}
sort(mp, mp + pmp);
pmp = unique(mp, mp + pmp) - mp;
for(int i = 0; i < pin; i++){
int pos = getIdx(in[i]);
vec[pos].push_back(i);
}
bfs();
for(int i = 0; i < pin; i++){
printf("%s", in[i].c_str());
if(dot[i] == 1) putchar(',');
if(dot[i] == 2) putchar('.');
if(i < pin - 1) putchar(' ');
}
puts("");
}
Queue - CodeForces - 141C
题意
已知每个人前面有多少个人比它高，要求构造一个符合已知的身高序列，无法构造输出-1
思路
填三个月前的坑
看到dalao的题解想了很久才懂，跪了 orz
按每个人前面有多少个人比它高升序排序，并记为h[i]（i为新的下标）
那么每个人前面有h[i]个人比它高，那么就有 i - h[i] - 1个人比它矮（假设身高各不相同）
这样子从左往右，对第i个人，设其身高为 i - h[i]，那么自然会有 i - h[i] - 1个比它矮，但是可能会有 h[i] - 1 个人比它高，这时候说明有一个人与 i - h[i] 同高，于是可以将 1 到 i - 1 下标中 >= i - h[i] 的都 +1，这样做的正确性在于，对于任意 1 到 i 的身高序列，都存在 1 到 i 的身高而且有且仅有一个，因此不会影响计算后面 i + 1, i + 2, … 的结果
这个构造方法真是太神奇了！
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
const int N = 3000 + 15;
const int M = 5133 + 15;
const int inf = 0x3f3f3f3f;
typedef long long ll;
struct Node{
string name;
int h;
int ans;
bool operator < (const Node& b) const { return h < b.h; }
};
Node a[N];
char s[N];
int main(){
int n;
while(~scanf("%d", &n)){
for(int i = 1; i <= n; i++){
scanf("%s%d", s, &a[i].h);
a[i].name = s;
}
sort(a + 1, a + n + 1);
bool flag = true;
for(int i = 1; i <= n; i++){
if(i <= a[i].h){
flag = false;
break;
}
}
if(flag){
for(int i = 1; i <= n; i++){
a[i].ans = i - a[i].h;
for(int j = 1; j < i; j++){
if(a[j].ans >= a[i].ans) a[j].ans++;
}
}
for(int i = 1; i <= n; i++){
printf("%s %d\n", a[i].name.c_str(), a[i].ans);
}
}else{
puts("-1");
}
}
}
Maximal GCD - CodeForces - 803C
题意
给定n和k，要求构造一个严格递增的序列，其个数为k，和为n，并且gcd最大，无法构造输出-1
思路
补三个月前的坑
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e5 + 15;
typedef long long ll;
bool used[N];
int prime[N];
int pp;
void getPrime(){
memset(used, true, sizeof(used));
pp = 0;
for(int i = 2; i < N; i++){
if(used[i]){
prime[pp++] = i;
}
for(int j = 0; i*prime[j] < N; j++){
used[i*prime[j]] = false;
if(i%prime[j] == 0){
break;
}
}
}
}
ll getMaxn(ll n, ll lval){
ll ret = 1;
for(ll i = 1; i*i <= n; i++){
if(n%i == 0){
if(i >= lval) ret = max(ret, n/i);
if(n/i >= lval) ret = max(ret, i);
}
}
return ret;
}
int main(){
getPrime();
ll n, k;
while(~scanf("%lld%lld", &n, &k)){
if((double)(k + 1) > (double)(2 * n/k)){
puts("-1");
continue;
}
ll lval = (k + 1) * k/2;
ll time = getMaxn(n, lval);
n /= time;
for(ll i = 1; i <= k; i++){
if(i < k) printf("%lld ", i*time);
else printf("%lld\n", time*(n - (k - 1) * k/2));
}
}
}
Planning - CodeForces - 853A
题意
给定序列n个整数和k，现在将整个序列向右偏移k个单位，你可以调整序列的顺序，但每一个数都不能调整到它原位置之前的位置，请你计算sum((p2 - p1) * a[i])的最小值，其中p2为现在的位置，p1为原位置
思路
贪心思想
用优先队列优先处理大的数，使每一个数移动到最邻近自身且没有被占用的位置（ >= 自身）
那要怎样才能知道第一个没被占用的位置呢，用并查集维护就可以了，对于每个数被占用后，直接并到它右边一个数所在的并查集即可，对于每一个要移动到的位置则查询其并查集的父节点即可
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <functional>
using namespace std;
typedef long long ll;
const int N = 600000 + 15;
struct Node{
int val, idx;
Node(int pval, int pidx): val(pval), idx(pidx) { }
bool operator < (const Node& b) const {
return val < b.val;
}
};
int ans[N];
int ft[N];
priority_queue<Node> que;
inline void init(){
for(int i = 1; i <= N - 1; i++) ft[i] = i;
}
int find(int x){
return x == ft[x] ? x : ft[x] = find(ft[x]);
}
void merge(int x, int y){
int p = find(x), q = find(y);
if(p != q) ft[q] = p;
}
int main(){
int n, k;
while(~scanf("%d%d", &n, &k)){
init();
ll sum = 0;
int tmp;
for(int i = 1; i <= n; i++){
scanf("%d", &tmp);
que.push(Node(tmp, i));
}
while(!que.empty()){
Node u = que.top();
que.pop();
int pos = max(k + 1, u.idx);
pos = find(pos);
merge(pos + 1, pos);
ans[u.idx] = pos;
sum += (ll)u.val*(ll)(pos - u.idx);
}
printf("%lld\n", sum);
for(int i = 1; i <= n; i++){
printf("%d ", ans[i]);
}
puts("");
}
return 0;
}
