不知不觉NOIP正在慢慢来了啊。
最近要开始刷些和NOIP难度类似的题目。
有空做了做NOIP2017的题，感觉和NOIP2018d2的难度区分有明显的感觉啊...
不多说了，结论\(a * b - a - b\)。
代码略。
大模拟题，细节有点多。
不过也还好，算是比较清新的那一种。
#include <bits/stdc++.h>
const int maxl = 110;
const int inf = 0x3f3f3f3f;
bool use[40];
std::string s, code[maxl];
int n, m, i, j, k, T, l, tf, te, co, O, etot, tot; bool cf;
int f[2];
bool flagerr; char v; int For;
struct node {
int var, st, ed, id; bool f;
node() { var = st = ed = f = id = 0; }
node(int _var,int _st,int _ed,int _f,int _id) {
var = _var; st = _st; ed = _ed; f = _f; id = _id;
}
};
std::stack<node> sta;
inline void cmax(int& a,int b) {
if(a < b)
a = b;
}
inline void clear() {
memset(use,0,sizeof(use));
tf = te = 0; flagerr = 0; co = 0; O = 0;
tot = 0; cf = 1; etot = 0;
while(!sta.empty())
sta.pop();
}
inline std::pair<int,int> getinfo(std::string s) {
int l = s.size(), L = 0, O = 0; bool F = 0;
bool f1 = 0, f2 = 0;
for(int i = 0;i < l;i++) {
char c = s[i];
if(isdigit(c)) {
if(!f1 && !f2)
f1 = 1, L = L * 10 + (c & 15);
else if(f1 && !f2)
L = L * 10 + (c & 15);
else
f2 = 1, O = O * 10 + (c & 15);
} else {
if(c == 'n')
F = 1;
if(f1)
f2 = 1;
}
}
if(!F)
O = 0;
return std::make_pair(L,O);
}
inline void trans(int& x,char c) {
if(c == 'n')
x = inf;
else
x = x * 10 + (c & 15);
}
inline void getfor(std::string s) {
int l = s.size(); bool f1 = 0, f2 = 0; int now = 0;
f[0] = 0; f[1] = 0;
for(int i = 0;i < l;i++) {
char c = s[i];
if((c >= 'a' && c <= 'z') && (c != 'n'))
v = c;
else if(isdigit(c) || c == 'n') {
if(f1 && !f2)
f1 = 1, trans(f[now],c);
else
f2 = 1, trans(f[now],c);
} else if(c == ' ') {
if(i == 1)
continue;
if(!f1)
f1 = 1;
else
now = 1, f2 = 1;
}
}
return;
}
int main() {
scanf("%d",&T);
std::getline(std::cin,s);
for(;T;T--) {
clear();
std::getline(std::cin,s);
std::pair<int,int> info = getinfo(s);
int l = info.first, o = info.second;
for(int i = 1;i <= l;i++)
std::getline(std::cin,code[i]);
int t = 0;
for(int i = 1;i <= l;i++) {
if(code[i][0] == 'E') {
t--;
if(t < 0) {
flagerr = 1;
break;
}
if(sta.top().f)
co--;
if(sta.top().id == etot)
cf = 1;
use[sta.top().var] = 0;
sta.pop();
} else {
getfor(code[i]); v = v - 'a';
t++;
if(use[v]) {
flagerr = 1;
break;
}
use[v] = 1;
int lco = co;
if(f[0] <= f[1]) {
if(cf && f[1] == inf && (!(f[0] == inf && f[1] == inf)))
co++;
} else {
if(cf)
cf = 0, etot = tot + 1;
}
cmax(O,co);
sta.push(node(v,f[0],f[1],(lco == co) ^ 1,++tot));
}
// printf("%d\n",etot);
}
if(t)
flagerr = 1;
if(flagerr) {
puts("ERR"); continue;
}
if(O == o) {
puts("Yes"); continue;
} else {
puts("No"); continue;
}
}
return 0;
}这题感觉没有其他人吹的那么难？
先预处理出正图中的最短路然后跑记忆化搜索。
我们先建一个反图，优化在于必然有些到不了终点的点，而反着跑可以忽略掉。
然后设当前传的参数为\(u\)和\(K\)，表示当前在第\(u\)点，原题中的\(k\)还剩\(K\)
转移的时候其实就是\(dfs(v,dis[u] + K - dis[v] - w)\)
这个的意思是如果不走最短路会对\(K\)造成的贡献。
然后就结束了。
好像很好写啊？
#include <bits/stdc++.h>
const int maxn = 1e5 + 10;
typedef long long ll;
template<class t> inline void read(t& res) {
res = 0; char ch = getchar(); bool neg = 0;
while(!isdigit(ch))
neg |= ch == '-', ch = getchar();
while(isdigit(ch))
res = (res << 1) + (res << 3) + (ch & 15), ch = getchar();
if(neg)
res = -res;
}
struct edge {
int v, w;
edge() { v = w = 0; }
edge(int _v,int _w) {
v = _v; w = _w;
}
};
std::vector<edge> g1[maxn], g2[maxn];
int dis[maxn], dp[maxn][60], ans;
int n, m, i, j, k, T, mod;
bool vis[maxn], zero[maxn][60];
struct node {
int u, d;
node() { u = d = 0; }
node(int _u,int _d) {
u = _u; d = _d;
}
inline friend bool operator < (node a,node b) {
return a.d >= b.d;
}
};
inline void dijk(int S) {
memset(dis,0x3f,sizeof(dis));
memset(vis,0,sizeof(vis));
std::priority_queue<node> pq;
pq.push(node(S,0)); dis[S] = 0;
while(!pq.empty()) {
int u = pq.top().u; pq.pop();
if(vis[u])
continue;
vis[u] = 1;
for(int i = 0, l = g1[u].size();i < l;i++) {
int v = g1[u][i].v, w = g1[u][i].w;
if(dis[u] + w < dis[v]) {
dis[v] = dis[u] + w;
pq.push(node(v,dis[v]));
}
}
}
}
int dfs(int u,int K) {
if(K < 0 || K > k)
return 0;
if(zero[u][K]) {
zero[u][K] = 0;
return -1;
}
if(~dp[u][K])
return dp[u][K];
zero[u][K] = 1; int res = 0;
for(int i = 0;i < g2[u].size();i++) {
int v = g2[u][i].v, w = g2[u][i].w;
int tmp = dfs(v,dis[u] + K - dis[v] - w);
if(tmp == -1) { zero[u][K] = 0; return -1; }
res = (res + tmp) % mod;
}
zero[u][K] = 0;
if(u == 1 && K == 0)
res++;
return dp[u][K] = res;
}
int main() {
read(T);
while(T--) {
read(n); read(m); read(k); read(mod);
for(int i = 1;i <= n;i++)
g1[i].clear(), g2[i].clear();
memset(zero,0,sizeof(zero));
memset(dp,-1,sizeof(dp));
for(int i = 1, u, v, w;i <= m;i++) {
read(u); read(v); read(w);
g1[u].push_back(edge(v,w));
g2[v].push_back(edge(u,w));
}
dijk(1); ans = 0; bool flag = 1;
for(int i = 0;i <= k;i++) {
int val = dfs(n,i); if(val == -1) { flag = 0; puts("-1"); break; }
ans = (ans + val) % mod;
}
if(flag)
printf("%d\n",ans);
}
}
原文：https://www.cnblogs.com/Sai0511/p/11238952.html