## 【codeforces】Codeforces Round #372 (Div. 2) 原

LOI_xczhw

### B

……好难

#### 第一种做法

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cctype>
using namespace std;
const int MAXN = 100000 + 5;
int n;
char c[MAXN];
int tong[26];
bool can(int x)
{
for(int i = 0;i < 26;i ++)
if(tong[c[x - i] - 'A'] > 1)
return false;
return true;
}
void fillall()
{
for(int i = 0;i < n;i ++)
if(c[i] == '?')
c[i] = 'A';
return;
}
int main()
{
gets(c);
n = strlen(c);
if(n < 26)
{
puts("-1");
return 0;
}
for(int i = 0;i < 25;i ++)
if(isalpha(c[i]))
tong[c[i] - 'A'] ++;
for(int i = 25;i < n;i ++)
{
if(isalpha(c[i - 26]))
tong[c[i - 26] - 'A'] --;
if(isalpha(c[i]))
tong[c[i] - 'A'] ++;
if(can(i))
{
int cha = 0;
while(tong[cha])
cha ++;
for(int j = i - 25;j <= i;j ++)
{
if(!isalpha(c[j]))
c[j] = cha + 'A',tong[cha] ++;
while(tong[cha])
cha ++;
}
fillall();
puts(c);
return 0;
}
}
puts("-1");
return 0;
}

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key

typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;

const int N = 10000;
int cnt[27];
string s; int n;

bool valid()
{
for(int i = 0; i < 26; i++)
{
if(cnt[i] >= 2) return false;
}
return true;
}

void fillall()
{
for(int i = 0; i < n; i++)
{
if(s[i] == '?') s[i] = 'A';
}
}

int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> s;
n = s.length();
if(n < 26) {cout << -1; return 0;}
for(int i = 25; i < n; i++)
{
memset(cnt, 0, sizeof(cnt));
for(int j = i; j >= i - 25; j--)
{
cnt[s[j]-'A']++;
}
if(valid())
{
//cout << "GG " << i << '\n';
int cur = 0;
while(cnt[cur]>0) cur++;
for(int j = i - 25; j <= i; j++)
{
if(s[j] == '?')
{
s[j] = cur + 'A';
cur++;
while(cnt[cur]>0) cur++;
}
}
fillall();
cout << s;
return 0;
}
}
cout << -1;
return 0;
}

#### 第二种做法

……md没区别……

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cctype>
using namespace std;
const int MAXN = 100000 + 5;
int n;
char c[MAXN];
int tong[26];
bool can(int x)
{
for(int i = 0;i < 26;i ++)
if(tong[c[x - i] - 'A'] > 1)
return false;
return true;
}
void fillall()
{
for(int i = 0;i < n;i ++)
if(c[i] == '?')
c[i] = 'A';
return;
}
int main()
{
gets(c);
n = strlen(c);
if(n < 26)
{
puts("-1");
return 0;
}
for(int i = 0;i < 26;i ++)
if(isalpha(c[i]))
tong[c[i] - 'A'] ++;
if(can(25))
{
int cha = 0;
while(tong[cha])
cha ++;
for(int j = 0;j <= 25;j ++)
{
if(!isalpha(c[j]))
c[j] = cha + 'A',tong[cha] ++;
while(tong[cha])
cha ++;
}
fillall();
puts(c);
return 0;
}
for(int i = 26;i < n;i ++)
{
if(isalpha(c[i - 26]))
tong[c[i - 26] - 'A'] --;
if(isalpha(c[i]))
tong[c[i] - 'A'] ++;
if(can(i))
{
int cha = 0;
while(tong[cha])
cha ++;
for(int j = i - 25;j <= i;j ++)
{
if(!isalpha(c[j]))
c[j] = cha + 'A',tong[cha] ++;
while(tong[cha])
cha ++;
}
fillall();
puts(c);
return 0;
}
}
puts("-1");
return 0;
}

#### 第三种做法

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cctype>
using namespace std;
const int MAXN = 100000 + 5;
int n;
char c[MAXN];
int tong[26];
int z;
bool can(int x)
{
return z == 26;
}
void fillall()
{
for(int i = 0;i < n;i ++)
if(c[i] == '?')
c[i] = 'A';
return;
}
int main()
{
gets(c);
n = strlen(c);
if(n < 26)
{
puts("-1");
return 0;
}
for(int i = 0;i < 26;i ++)
if(isalpha(c[i]))
z += !tong[c[i] - 'A'],tong[c[i] - 'A'] ++;
else
z ++;
if(can(25))
{
int cha = 0;
while(tong[cha])
cha ++;
for(int j = 0;j <= 25;j ++)
{
if(!isalpha(c[j]))
c[j] = cha + 'A',tong[cha] ++;
while(tong[cha])
cha ++;
}
fillall();
puts(c);
return 0;
}
for(int i = 26;i < n;i ++)
{
if(isalpha(c[i - 26]))
z -= !(-- tong[c[i - 26] - 'A']);
if(isalpha(c[i]))
z += !(tong[c[i] - 'A'] ++);
if(c[i] == '?')
z ++;
if(c[i - 26] == '?')
z --;
if(can(i))
{
int cha = 0;
while(tong[cha])
cha ++;
for(int j = i - 25;j <= i;j ++)
{
if(!isalpha(c[j]))
c[j] = cha + 'A',tong[cha] ++;
while(tong[cha])
cha ++;
}
fillall();
puts(c);
return 0;
}
}
puts("-1");
return 0;
}

╮(╯▽╰)╭

QAQ

### D

#### 题目大意

1、如果不考虑可变边，从s到t的最短路小于L的话，那么输出NO

2、将所有可变边的权值赋为1，显然，这是在所有可以从原图变化而来的图中从s到e的最短路最短的一张图，如果这张图从s到e的最短路仍然大于L，那么输出NO

3、如果不属于以上两种情况，那么我们就可以通过分配权值使得从s到e的最短路长度恰好为L

First, consider all paths from s to e that has at least one 0 weight edge, as changing weights won’t affect the other paths.

//嗯……还好理解

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
typedef long long LL;
const LL MAXN = 1000 + 5;
const LL MAXM = 10000 + 5;
const LL INF = 1e18;
struct edge
{
LL f,t,v;
bool is_0,is_qd;
}l[MAXM << 1];
LL first[MAXN],next[MAXM << 1],tot;
void init()
{
memset(first,0xfff,sizeof(first));
tot = 0;
return;
}
void build(LL f,LL t,LL v,bool zer0)
{
l[++tot] = (edge){f,t,v,zer0,false};
next[tot] = first[f];
first[f] = tot;
return;
}
struct zt
{
LL u,v;
bool operator < (const zt &b)const
{
return v > b.v;
}
};
priority_queue <zt> q;
LL dis[MAXN],done[MAXN];
LL last[MAXN];
void dij(LL s,LL e)
{
memset(dis,0x3f,sizeof(dis));
memset(done,0,sizeof(done));
while(!q.empty())
q.pop();
dis[s] = 0;
q.push((zt){s,0});
while(!q.empty())
{
zt x = q.top();
q.pop();
LL u = x.u;
if(done[u])
continue;
done[u] = true;
if(u == e)
return;
for(int i = first[u];i != -1;i = next[i])
{
LL v = l[i].t;
if(dis[v] > dis[u] + l[i].v)
{
dis[v] = dis[u] + l[i].v;
q.push((zt){v,dis[v]});
}
}
}
return;
}
LL dist[MAXN];
void dij_remember(int s,int e)
{
memset(dist,0x3f,sizeof(dist));
memset(done,0,sizeof(done));
while(!q.empty())
q.pop();
dist[s] = 0;
q.push((zt){s,0});
last[s] = -1;
while(!q.empty())
{
zt x = q.top();
q.pop();
LL u = x.u;
if(done[u])
continue;
done[u] = true;
if(u == e)
return;
for(int i = first[u];i != -1;i = next[i])
{
LL v = l[i].t;
if(dist[v] > dist[u] + l[i].v)
{
dist[v] = dist[u] + l[i].v;
last[v] = i;
q.push((zt){v,dist[v]});
}
}
}
return;
}
LL another(LL x)
{
if(x & 1)
return x + 1;
else
return x - 1;
}
LL n,m,L,s,e;
LL f,t,v;
int main()
{
init();
scanf("%I64d %I64d %I64d %I64d %I64d",&n,&m,&L,&s,&e);
for(int i = 1;i <= m;i ++)
{
bool flag = false;
scanf("%I64d %I64d %I64d",&f,&t,&v);
if(!v)
v = INF,flag = true;
build(f,t,v,flag);
build(t,f,v,flag);
}
dij(s,e);
if(dis[e] < L)
{
puts("NO");
return 0;
}
for(int i = 1;i <= tot;i ++)
if(l[i].is_0)
l[i].v = 1;
dij_remember(s,e);
if(dist[e] > L)
{
puts("NO");
return 0;
}
puts("YES");
LL k = last[e];
while(~k)
{
if(l[k].is_0)
l[k].is_qd = l[another(k)].is_qd = true;
k = last[l[k].f];
}
for(int i = 1;i <= tot;i ++)
if(l[i].is_0 && !l[i].is_qd)
l[i].v = l[another(i)].v = INF;
k = last[e];
for(int i = 1;i <= tot;i ++)
{
if(l[i].is_qd)
{
l[i].v = l[another(i)].v = INF;
dij(s,e);
if(dis[e] > L)
{
l[i].v = l[another(i)].v = L - dist[e] + 1;
break;
}
else
l[i].v = l[another(i)].v = 1;
}
}
for(int i = 1;i <= tot;i += 2)
printf("%I64d %I64d %I64d\n",l[i].f,l[i].t,l[i].v);
return 0;
}

A:停停停停停！这是不对的！你不碰这条边的时候不能把它重置成1而是要让它是INF！！

5 5 4 1 4
1 2 3
1 5 0
2 4 0
2 5 0
2 4 2

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
typedef long long LL;
const LL MAXN = 1000 + 5;
const LL MAXM = 10000 + 5;
const LL INF = 1e18;
struct edge
{
LL f,t,v;
bool is_0,is_qd;
}l[MAXM << 1];
LL first[MAXN],next[MAXM << 1],tot;
void init()
{
memset(first,0xfff,sizeof(first));
tot = 0;
return;
}
void build(LL f,LL t,LL v,bool zer0)
{
l[++tot] = (edge){f,t,v,zer0,false};
next[tot] = first[f];
first[f] = tot;
return;
}
struct zt
{
LL u,v;
bool operator < (const zt &b)const
{
return v > b.v;
}
};
priority_queue <zt> q;
LL dis[MAXN],done[MAXN];
LL last[MAXN];
void dij(LL s,LL e)
{
memset(dis,0x3f,sizeof(dis));
memset(done,0,sizeof(done));
while(!q.empty())
q.pop();
dis[s] = 0;
q.push((zt){s,0});
while(!q.empty())
{
zt x = q.top();
q.pop();
LL u = x.u;
if(done[u])
continue;
done[u] = true;
if(u == e)
return;
for(int i = first[u];i != -1;i = next[i])
{
LL v = l[i].t;
if(dis[v] > dis[u] + l[i].v)
{
dis[v] = dis[u] + l[i].v;
q.push((zt){v,dis[v]});
}
}
}
return;
}
LL dist[MAXN];
void dij_remember(int s,int e)
{
memset(dist,0x3f,sizeof(dist));
memset(done,0,sizeof(done));
while(!q.empty())
q.pop();
dist[s] = 0;
q.push((zt){s,0});
last[s] = -1;
while(!q.empty())
{
zt x = q.top();
q.pop();
LL u = x.u;
if(done[u])
continue;
done[u] = true;
if(u == e)
return;
for(int i = first[u];i != -1;i = next[i])
{
LL v = l[i].t;
if(dist[v] > dist[u] + l[i].v)
{
dist[v] = dist[u] + l[i].v;
last[v] = i;
q.push((zt){v,dist[v]});
}
}
}
return;
}
LL another(LL x)
{
if(x & 1)
return x + 1;
else
return x - 1;
}
LL n,m,L,s,e;
LL f,t,v;
int main()
{
init();
scanf("%I64d %I64d %I64d %I64d %I64d",&n,&m,&L,&s,&e);
for(int i = 1;i <= m;i ++)
{
bool flag = false;
scanf("%I64d %I64d %I64d",&f,&t,&v);
if(!v)
v = INF,flag = true;
build(f,t,v,flag);
build(t,f,v,flag);
}
dij(s,e);
if(dis[e] < L)
{
puts("NO");
return 0;
}
for(int i = 1;i <= tot;i ++)
if(l[i].is_0)
l[i].v = 1;
dij_remember(s,e);
if(dist[e] > L)
{
puts("NO");
return 0;
}
puts("YES");
LL k = last[e];
while(~k)
{
if(l[k].is_0)
l[k].is_qd = l[another(k)].is_qd = true;
k = last[l[k].f];
}
for(int i = 1;i <= tot;i ++)
if(l[i].is_0 && !l[i].is_qd)
l[i].v = l[another(i)].v = INF;
k = last[e];
for(int i = 1;i <= tot;i ++)
{
if(l[i].is_qd)
{
l[i].v = l[another(i)].v = INF;
dij(s,e);
if(dis[e] > L)
{
l[i].v = l[another(i)].v = 1;
dij(s,e);
l[i].v = l[another(i)].v = L - dis[e] + 1;
break;
}
}
}
for(int i = 1;i <= tot;i += 2)
printf("%I64d %I64d %I64d\n",l[i].f,l[i].t,l[i].v);
return 0;
}

P.S

### LOI_xczhw

Codeforces Round #500 (Div. 2) BC

CodeForces 1013B And CodeForces 1013C Photo of The Sky B 可以发现只有一次与操作是有意义的，所以答案只有-1，0，1，2四种情况 2 #define show(a) cout << #a << " = " << a << endl; 3 ......

cjc7373
2018/07/30
0
0
Codeforces Round #510 (Div. 2) A - Benches

bryce1010
2018/09/18
0
0
【水题】Codeforces Round #510 (Div. 2) B. Vitamins

bryce1010
2018/09/18
0
0
Codeforces积分系统介绍

2018/05/28
0
0
Educational Codeforces Round 72 (Rated for Div. 2)-D. Coloring Edges-拓扑排序

Educational Codeforces Round 72 (Rated for Div. 2)-D. Coloring Edges-拓扑排序 【Problem Description】 给你一个有向图，给用最少的颜色给每条边染色，要保证不存在一个环中的所有边都是...

__Simon
09/16
0
0

nginx反向代理+负载均衡+服务器宕机解决办法

Jack088
11分钟前
2
0

18分钟前
2
0

22分钟前
2
0

25分钟前
2
0

simpower
26分钟前
2
0