[BZOJ 2118]墨墨的等式
论如何把数论乱搞和图论乱搞出在一起……
这个题由于要求[tex]x\ge 0[/tex]，所以不能gcd乱搞。我们可以先取[tex]\{a_n\}[/tex]的最小值[tex]p[/tex]（忽略为0的情况，为啥取最小值待会再说），对方程两边模[tex]p[/tex]。然后对于任何能使某个同余方程成立的[tex]\{x_n\}[/tex]，将其中所有[tex]x_i[/tex]同时加任意个[tex]p[/tex]，同余方程都成立。
取模后，[tex]B\in Z_p[/tex]，所以说只要对于[tex]Z_p[/tex]中的每个数找出最小的一组合法解即能推出其他解（所以说，剩余系越少效率越高，这也就要求取的[tex]a_i[/tex]要小）。不过这个最小的一组合法解怎么找？
我们先找出任意一个合法[tex]B[/tex]（比如说0吧），然后尝试加上[tex]a_i[/tex]，就可以推出其他[tex]B\in Z_p[/tex]的最小解。这个应用当然是需要最短路辣。
求出来的最短路，表示的是取最小解时的[tex]B[/tex]。这样的话就可以推出某个前缀区间中合法[tex]B[/tex]的个数（能加多少[tex]p[/tex]，就有多少个，注意不要忽略加0个的情况），并且答案符合区间减法，最后做差分即可。
注意忽略[tex]a_i=0[/tex]的情况（相当于不存在）。
代码：
/**************************************************************
Problem: 2118
User: danihao123
Language: C++
Result: Accepted
Time:1952 ms
Memory:5508 kb
****************************************************************/
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#ifdef DEBUG
#include <cassert>
#endif
using namespace std;
typedef long long ll;
const int maxn=15;
const ll INF=0x7f7f7f7f7f7f7f7f;
ll A[maxn];
bool inQueue[500005];
ll d[500005];
int n;
ll minv;
inline void SPFA(){
register int i,u,to;
queue<int> Q;
memset(d,0x7f,sizeof(d));
d[0]=0;
Q.push(0);
inQueue[0]=true;
#ifdef DEBUG
assert(d[1]==INF);
#endif
while(!Q.empty()){
u=Q.front();
Q.pop();
inQueue[u]=false;
for(i=1;i<=n;i++){
to=(u+A[i])%minv;
if(d[u]<INF && d[u]+A[i]<d[to]){
d[to]=d[u]+A[i];
if(!inQueue[to]){
Q.push(to);
inQueue[to]=true;
}
}
}
}
}
inline ll Calc(ll x){
register ll ans=0;
register int i=0;
for(i=0;i<minv;i++)
if(d[i]<=x)
ans+=(x-d[i])/minv+1;
return ans;
}
int main(){
ll l,r;
register int i;
scanf("%d%lld%lld",&n,&l,&r);
minv=0x7fffffff;
for(i=1;i<=n;i++){
scanf("%d",&A[i]);
if(!A[i]){
i--;
n--;
continue;
}
minv=min(minv,A[i]);
}
SPFA();
printf("%lld\n",Calc(r)-Calc(l-1));
return 0;
}
[BZOJ 3436]小K的农场
差分约束系统的可行性问题啊……
按照要求连边然后SPFA判负环即可。
代码：
/**************************************************************
Problem: 3436
User: danihao123
Language: C++
Result: Accepted
Time:9224 ms
Memory:1488 kb
****************************************************************/
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
const int maxn=10005,maxm=30005;
typedef long long ll;
#define REP(i,n) for(i=1;i<=(n);i++)
#define CL_ARR(i,x) memset(i,x,sizeof(i))
#define GRAPH_REP(i,u) for(i=first[(u)];i;i=next[i])
int n;
namespace Graph{
int first[maxn];
int next[maxm],to[maxm];
ll dist[maxm];
int tot=0;
inline void AddEdge(int u,int v,ll d){
tot++;
next[tot]=first[u];
first[u]=tot;
to[tot]=v;
dist[tot]=d;
}
bool inQueue[maxn];
ll d[maxn];
int cnt[maxn];
bool SPFA(){
register int i,u;
queue<int> Q;
REP(i,n){
inQueue[i]=true;
Q.push(i);
}
while(!Q.empty()){
u=Q.front();
Q.pop();
inQueue[u]=false;
GRAPH_REP(i,u){
if(d[to[i]]>d[u]+dist[i]){
d[to[i]]=d[u]+dist[i];
if(!inQueue[to[i]]){
Q.push(to[i]);
inQueue[to[i]]=true;
if(++cnt[to[i]]>n)
return false;
}
}
}
}
return true;
}
};
int main(){
int m,opt,a,b,c;
register int i;
scanf("%d%d",&n,&m);
REP(i,m){
scanf("%d%d%d",&opt,&a,&b);
if(opt==1){
scanf("%d",&c);
Graph::AddEdge(a,b,-c);
}else{
if(opt==2){
scanf("%d",&c);
Graph::AddEdge(b,a,c);
}else{
Graph::AddEdge(a,b,0);
Graph::AddEdge(b,a,0);
}
}
}
if(Graph::SPFA())
puts("Yes");
else
puts("No");
return 0;
}
[BZOJ 1715]虫洞
呜……这题现在才A
这道题就是给一个图让判断有没有负环，没什么难度
然后……我写邻接表竟然开小内存了……
尽管如此我感觉我写此题时的代码风格还是不错的，比较值得学习
代码：
/**************************************************************
Problem: 1715
User: danihao123
Language: C++
Result: Accepted
Time:92 ms
Memory:920 kb
****************************************************************/
#include <cstdio>
#include <queue>
#include <cstring>
#include <cctype>
using namespace std;
const int maxn=501,maxm=5201;
namespace Graph{
int n;
int first[maxn];
int next[maxm],to[maxm],dist[maxm];
int tot=0;
inline void AddEdge(int u,int v,int d){
tot++;
next[tot]=first[u];
first[u]=tot;
to[tot]=v;
dist[tot]=d;
}
inline void ClearGraph(){
memset(first,0,sizeof(first));
memset(next,0,sizeof(next));
memset(to,0,sizeof(to));
memset(dist,0,sizeof(dist));
tot=0;
}
int cnt[maxn];
bool inQueue[maxn];
int d[maxn];
bool SPFA(){
register int i,u;
queue<int> Q;
memset(cnt,0,sizeof(cnt));
memset(inQueue,0,sizeof(inQueue));
for(i=1;i<=n;i++){
d[i]=0;
cnt[i]=1;
inQueue[i]=true;
Q.push(i);
}
while(!Q.empty()){
u=Q.front();
Q.pop();
inQueue[u]=false;
for(i=first[u];i;i=next[i]){
if(d[to[i]]>d[u]+dist[i]){
d[to[i]]=d[u]+dist[i];
if(!inQueue[to[i]]){
Q.push(to[i]);
inQueue[to[i]]=true;
if(++cnt[to[i]]>n)
return true;
}
}
}
}
return false;
}
};
inline int readint(){
register char c;
register int temp=0;
c=getchar();
while(!isdigit(c))
c=getchar();
while(isdigit(c)){
temp=temp*10+c-'0';
c=getchar();
}
return temp;
}
int main(){
register int i,m,w,u,v,d;
int F;
F=readint();
while(F--){
Graph::n=readint();
m=readint();
w=readint();
Graph::ClearGraph();
for(i=1;i<=m;i++){
u=readint();
v=readint();
d=readint();
Graph::AddEdge(u,v,d);
Graph::AddEdge(v,u,d);
}
for(i=1;i<=w;i++){
u=readint();
v=readint();
d=readint();
Graph::AddEdge(u,v,-d);
}
if(Graph::SPFA())
puts("YES");
else
puts("NO");
}
return 0;
}
