思路：
不妨设 a < b
假设答案为 x
若
? x≡ma (mod b)(1 ≤ m ≤ b?1)
即
? x=ma+nb ( 1 ≤ m ≤ b?1)
显然当 n ≥ 0 时 x 可以用 a , b 表示出来，不合题意。
因此当 n = -1 时 x 取得最大值，此时 x = ma - b 。
显然当 m取得最大值 b - 1 时 x 最大，此时 x = (b - 1)a - b = ab - a - b
因此 a, b 所表示不出的最大的数是 ab - a - b
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#define ll long long
#define InF 2147483647
using namespace std;
/*====================================快读*/
int read()
{
int x=0,f=1;
char c=getchar();
while(c<‘0‘||c>‘9‘)
{
if(c==‘-‘)
f=-1;
c=getchar();
}
while(c>=‘0‘&&c<=‘9‘)
{
x=(x<<3)+(x<<1)+(c^48);
c=getchar();
}
return x*f;
}
/*======================================定义变量*/
ll a,b;
/*====================================自定义函数*/
/*========================================主程序*/
int main()
{
// freopen("math.in","r",stdin);
// freopen("math.out","w",stdout);
a=read();
b=read();
printf("%ld",a*b-a-b);
return 0;
}
Tips：
不开 long long 见祖宗。
输出格式应与定义格式保持一致。
思路：
这不就是个大模拟吗？？
模拟好啊，模拟无脑，我最会打模拟了/得意。
最后得分：\(0 pts\)……
ERR跳出后如何读下一组数据？
一直读，直到含有大写字母O
若遇到初值大于末值应如何处理？
标记一下，后面的只判断ERR
退出循环时更改什么判断什么取消什么？
循环数取max，若之前标记过，取消即可，同时变量也要取消
代码：
#include<bits/stdc++.h>
using namespace std;
string a,b; //a,b循环使用
int c,d,e,f[27],g[27],h,k,l[100],m,n,T;
//c是有几个句子，d是题目给的复杂度是多少
//e是当前在几重循环，f[]是判断变量是否使用过
//g[]是存下每个循环的变量，h是当前复杂度是多少(与e不同)
//k是判断下面程序是否进行，l[]是存下哪几个循环加了复杂度
//m是当前最大复杂度，n是存下k=1时的循环数
//o是数据组数
void csh()
{
c=0;
d=0;
m=0;
n=0;
e=0;
h=0;
k=0; //初始化，剩余数据组数-1
memset(f,0,sizeof(f));
memset(l,0,sizeof(l)); //初始化
}
int main()
{
cin>>T; //读入数据组数
while(T--)
{
while(1)
{
a=b;
cin>>b;
if(b[0]==‘O‘)
break;
} //读入，当b[0]=‘O‘时停下，保证ERR时下一个继续运行
for(int i=0; i<a.length(); i++) c=c*10+a[i]-‘0‘; //取出题目给的句子数量
for(int i=4; i<b.length()-1; i++) d=d*10+b[i]-‘0‘; //取出题目给的时间复杂度 O(1)不影响
while(c>0)
{
c--;
cin>>a; //读入F 或 E ,句子数-1
if(a[0]==‘F‘)
{ //如果是F
e++;
cin>>a; //当前循环数+1，读入变量
if(f[a[0]-96])
e=-1; //如果被用过，标记ERR
else
{
f[a[0]-96]=1;
g[e]=a[0]-96;
} //没用过就标记用过，并存起来
cin>>a>>b; //读入变量初值和末值
if(a[0]!=‘n‘&&b[0]==‘n‘&&k==0)
{
h++;
l[e]=1;
}//如果a是数字，b是n，而且可以运行，那么当前复杂度+1，记下循环数
else if(((a.length()==b.length()&&a>b)||(a.length()>b.length())||(a[0]==‘n‘&&b[0]!=‘n‘))&&k==0)
{
k=1;n=e;
}
//如果a>b(n 4,45 12,24 9),而且可以运行，那么标记下面的都不能运行，记下当前循环
//像5 8，76 78, n n 之类的不影响，不需要处理
}
else
{
//如果是E
m=m>h ? m : h;
f[g[e]]=0; //将最大复杂度更改 ，变量标记没用过
if(l[e]==1)
{
h--;
l[e]=0;
} //如果当前循环加了复杂度，当前复杂度-1，标记清空
e--; //当前循环数-1
if(n>0&&e<n)
{
k=0;
n=0;
} //如果跳出了n标记的那个循环，那么接下来的循环可以运行，标记清空
}
if(e==-1)
{
printf("ERR\n");
c=-1;
}
//如果e<0(变量用过或者E过多)，那么输出ERR，跳出循环
}
if(e>0)
printf("ERR\n"); //如果e>0(F过量)，那么输出ERR，跳出循环
if(e==0&&m==d)
printf("Yes\n"); //如果F,E相同而且最大复杂度等于题目给的复杂度，输出Yes
if(e==0&&m!=d)
printf("No\n"); //如果F,E相同而且最大复杂度不等于题目给的复杂度，输出No
}
return 0;
}
Tips:
思路：
题目化简：一个有向无重边自环图，设D为从1号点走到n号点的最短距离。问有多少条从1到n的路径长度不超过D+K。KK为给定的值，且K≤50如果有无数条，输出-1
下面有dis[i]表示i号点到n号点的最短路径长度。
设\(f[i][j]\)表示从i号点走到n号点，走了j的多余路径的方案数。就有如下转移方程式:
\(f[i][j]\)=\(\sum\limits_{i,v之间有边}\)\(f[v][j-(dis[v]+w-dis[i])]\)
记忆化搜索即可。
注意到如果出现了无数条路径，肯定出现了0环。也就是某一个状态被访问了两次。记忆化搜索的过程中标记一下即可。
代码：
#include<cstdio>
#include<iostream>
#include<ctime>
#include<queue>
#include<cstring>
#include<string>
using namespace std;
typedef long long ll;
const int N = 200010;
ll read() {
ll x = 0,f = 1;char c = getchar();
while(c < ‘0‘ || c > ‘9‘) {
if(c == ‘-‘) f = -1;
c = getchar();
}
while(c >= ‘0‘ && c <= ‘9‘) {
x = x * 10 + c - ‘0‘;
c = getchar();
}
return x * f;
}
struct node {
int v,nxt,w;
}e[N << 1],E[N << 1];
int head[N],ejs;
void add(int u,int v,int w) {
e[++ejs].v = v;e[ejs].nxt = head[u];head[u] = ejs;e[ejs].w = w;
}
int head2[N],ejs2;
void add2(int u,int v,int w) {
E[++ejs2].v = v;E[ejs2].w = w;E[ejs2].nxt = head2[u];head2[u] = ejs2;
}
queue<int>q;
int n,m,K,mod,dis[N],vis[N];
void spfa(int U) {
memset(dis,0x3f,sizeof(dis));
memset(vis,0,sizeof(vis));
dis[U] = 0;
q.push(U);
while(!q.empty()) {
int u = q.front();q.pop();vis[u] = 0;
for(int i = head2[u];i;i = E[i].nxt) {
int v = E[i].v;
if(dis[v] > dis[u] + E[i].w) {
dis[v] = dis[u] + E[i].w;
if(!vis[v]) {
vis[v] = 1;q.push(v);
}
}
}
}
}
int bz[N][60],f[N][60];
int dfs(int u,int x) {
if(bz[u][x] == 2) return f[u][x];
if(bz[u][x] == 1) return -1;
bz[u][x] = 1;
for(int i = head[u];i;i = e[i].nxt) {
int v = e[i].v;
int w = x - (dis[v] + e[i].w - dis[u]);
if(w < 0 || w > K) continue;
int k = dfs(v,w);
if(k == -1) return -1;
f[u][x] += k;
f[u][x] %= mod;
}
bz[u][x] = 2;
return f[u][x];
}
int main() {
int T = read();
while(T--) {
memset(head,0,sizeof(head));
ejs2 = 0;
memset(head2,0,sizeof(head2));
ejs = 0;
n = read(),m = read(),K = read(),mod = read();
memset(f,0,sizeof(f));
memset(bz,0,sizeof(bz));
for(int i = 1;i <= m;++i) {
int u = read(),v = read(),w = read();
add(u,v,w);
add2(v,u,w);
}
spfa(n);
f[n][0] = 1;
int ans = 0;
for(int i = 0;i <= K;++i) {
int k = dfs(1,i);
if(k == -1) {
ans = -1;break;
}
ans += k;
ans %= mod;
}
printf("%d\n",ans);
}
return 0;
}
Tips:
其实这题 \(DJ+DFS\) 可以跑过 \(60pts\)，但是遇到 \(0\) 环就无能为力了。
原文：https://www.cnblogs.com/Frather/p/13916742.html