Lvat_s Blog

据说网络流写得好也能过……orz常数帝们

我自己是看了周冬的论文——他来自芜湖一中。膜拜前辈！orzzzz

S-T图直接最短路就行了，注意建图即可。

#include<cstdio>
#include<vector>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;

int n,m,en,h[2000005],D[2000005],f[2000005],S,T;

struct Edge{
int b,v,next;
}e[7000005];

struct Node{
int u,v;
bool operator< (const Node &x) const{
return v>x.v?1:0;
}
};

priority_queue<Node> Q;

void add(int sa,int sb,int sc){
e[++en].b=sb;
e[en].v=sc;
e[en].next=h[sa];
h[sa]=en;
}

void Dijkstra(){
memset(D,120,sizeof(D));
memset(f,0,sizeof(f));
while(!Q.empty())Q.pop();
Node tmp;
tmp.u=S;
D[S]=0;
tmp.v=0;
Q.push(tmp);
while(!Q.empty()){
    int u=Q.top().u;
    Q.pop();
    if(f[u])continue;
    if(u==T){printf("%d\n",D[T]);break;}
    f[u]=1;
    for(int i=h[u];i!=-1;i=e[i].next){
        int v=e[i].b;
        if(!f[v] && D[u]+e[i].v<D[v]){
            D[v]=D[u]+e[i].v;
            tmp.u=v;
            tmp.v=D[v];
            Q.push(tmp);
        }
    }
}
}

void Scanf(int &s){
char x;
while((x=getchar())<'0' || x>'9');
s=x-'0';
while((x=getchar())>='0' && x<='9')s=s*10+x-'0';
}

int main(){
freopen("1001.in","r",stdin);
freopen("1001.out","w",stdout);
Scanf(n);
Scanf(m);
S=0;
T=(n-1)*(m-1)*2+1;
memset(h,-1,sizeof(h));
en=0;
if(n==1 || m==1){
    n=max(n,m);
    int ans=2147483647,w;
    for(int i=1;i<n;i++){
        Scanf(w);
        ans=min(ans,w);
    }
    printf("%d\n",ans==2147483647?0:ans);
    return 0;
}
for(int i=0;i<=n-1;i++){
    for(int j=1;j<=m-1;j++){
        int sa,sb,sc;
        Scanf(sc);
        sa=((i-1)*(m-1)+j)*2-1;
        sb=(i*(m-1)+j)*2;
        if(i==0)sa=T;
        else if(i==n-1)sb=S;
        add(sa,sb,sc);
        add(sb,sa,sc);
    }
}
for(int i=1;i<=n-1;i++){
    for(int j=0;j<=m-1;j++){
        int sa,sb,sc;
        Scanf(sc);
        sa=((i-1)*(m-1)+j)*2;
        sb=((i-1)*(m-1)+j+1)*2-1;
        if(j==0)sa=S;
        else if(j==m-1)sb=T;
        add(sa,sb,sc);
        add(sb,sa,sc);
    }
}
for(int i=1;i<=n-1;i++){
    for(int j=1;j<=m-1;j++){
        int sa,sb,sc;
        Scanf(sc);
        sa=((i-1)*(m-1)+j)*2;
        sb=((i-1)*(m-1)+j)*2-1;
        add(sa,sb,sc);
        add(sb,sa,sc);
    }
}
Dijkstra();
return 0;
}

你不觉得这个博客太水了么？

对于我这种没前途的人，也只能靠刷水过日子了……

普通的最小生成树。

#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;

int n,m,f[305];

struct Node{
int a,b,v;
}a[90005];

int cmp(const void *a,const void *b){
return (*(Node *)a).v>(*(Node *)b).v?1:-1;
}

int Find(int i){
return i==f[i]?i:f[i]=Find(f[i]);
}

void Union(int sa,int sb){
if(sa>sb)f[sa]=sb;
else f[sb]=sa;
}

int main(){
freopen("1083.in","r",stdin);
freopen("1083.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)f[i]=i;
for(int i=1;i<=m;i++){
    scanf("%d %d %d",&a[i].a,&a[i].b,&a[i].v);
}
qsort(a,m,sizeof(Node),cmp);
int fff=0;
for(int i=1;i<=m;i++){
    if(Find(a[i].a)!=Find(a[i].b)){fff++;Union(Find(a[i].a),Find(a[i].b));if(fff==n-1){printf("%d %d\n",n-1,a[i].v);}}
}
return 0;
}

我也是只会做这种题了囧……

仔细分析这个图，手画几个N，就能得出规律……

ans(n)+1=sigma(phi[i])(i=2...n-1)

于是代码就出来了……线筛phi谁不会……

#include<cstdio>
int n,eu[400005],ans=2;

void E(){
for(int i=1;i<=400000;i++)eu[i]=i;
for(int i=2;i<=400000;i++){
	if(eu[i]==i){
		for(int j=i;j<=400000;j+=i){
			eu[j]=eu[j]/i*(i-1);
		}
	}
}
}

int main(){
freopen("2190.in","r",stdin);
freopen("2190.out","w",stdout);
scanf("%d",&n);
E();
for(int i=2;i<n;i++)ans+=eu[i];
printf("%d\n",ans*2-1);
return 0;
}

我又来水了……

这题是标准的Nim游戏。没错，太标准了，一模一样。

只要知道Bouton定理就完全无压力……

#include<cstdio>
int t,n;
int main(){
freopen("1022.in","r",stdin);
freopen("1022.out","w",stdout);
scanf("%d",&t);
while(t--){
    int tp,flg=0;
    scanf("%d",&n);
    n--;
    scanf("%d",&tp);
    if(tp>1)flg=1;
    while(n--){
        int tp2;
        scanf("%d",&tp2);
        if(tp2>1)flg=1;
        tp^=tp2;
    }
    if((tp==0 && flg!=0) || (tp!=0 && flg==0))printf("Brother\n");
    else printf("John\n");
}
return 0;
}

我最喜欢的题目就是简单题了。（没办法我是蒟蒻）

差分约束现学现卖

这题搞个差分约束，注意数据有个超长的链，倒着加边就行。

#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
//不要问为什么每个数组都是1000005……因为方便~
int n,k,en,h[1000005],cir[1000005],d[1000005],flg[1000005];
long long ans=0;

struct Edge{
int b,v,next;
}e[1000005];

void add(int sa,int sb,int sc){
e[++en].b=sb;
e[en].v=sc;
e[en].next=h[sa];
h[sa]=en;
}

int spfa(){
//memset(d,0x3f,sizeof(d));
queue<int> Q;
Q.push(0);
d[0]=0;
flg[0]=1;
cir[0]=1;
int u,v;
while(!Q.empty()){
    u=Q.front();
    Q.pop();
    flg[u]=0;
    for(int i=h[u];i;i=e[i].next){
        v=e[i].b;
        if(d[u]+e[i].v>d[v]){
            d[v]=d[u]+e[i].v;
            if(++cir[v]>=n)return 1;
            if(!flg[v]){
                Q.push(v);
                flg[v]=1;
            }
        }
    }
}
return 0;
}

int main(){
freopen("2330.in","r",stdin);
freopen("2330.out","w",stdout);
scanf("%d %d",&n,&k);
for(int i=0;i<k;i++){
int x,a,b;
scanf("%d %d %d",&x,&a,&b);
if(x==1){add(a,b,0);add(b,a,0);continue;}
if(x==2){if(a==b){printf("-1\n");return 0;}add(a,b,1);continue;}
if(x==3){add(b,a,0);continue;}
if(x==4){if(a==b){printf("-1\n");return 0;}add(b,a,1);continue;}
if(x==5){add(a,b,0);continue;}
}
for(int i=n;i>0;i--)add(0,i,1);
if(spfa()){printf("-1\n");return 0;}
//for(int i=1;i<=n;i++)printf("%d\n",d[i]);
for(int i=1;i<=n;i++)ans+=d[i];
printf("%lld\n",ans);
return 0;
}

大家好，我是传奇蒟蒻！

刚刚玩了一下kenji's life，在CTSC时被虐了……

还是太弱了啊，游戏里都被虐

先写简单题感受一下神犇们的嘲讽。

这题使用小根堆维护，然后套个贪心就没了。

#include<cstdio>
#include<cstdlib>
#include<queue>
#include<algorithm>
using namespace std;

int n,ans=0,now=0;

struct Node{
int t1,t2,flg;
friend bool operator < (const Node&a ,const Node&b){
return a.t1<b.t1?1:0;
}
}a[150005];

priority_queue <Node> Q;

int cmp(const void *a,const void *b){
if((*(Node *)a).t2==(*(Node *)b).t2)return (*(Node *)a).t1-(*(Node *)b).t1;
return (*(Node *)a).t2-(*(Node *)b).t2;
}

int main(){
freopen("1029.in","r",stdin);
freopen("1029.out","w",stdout);
scanf("%d",&n);
for(int i=0;i<n;i++){
    scanf("%d %d",&a[i].t1,&a[i].t2);
    a[i].flg=0;
}
qsort(a,n,sizeof(Node),cmp);
for(int i=0;i<n;i++){
    if(a[i].t2>=a[i].t1+now){
        ans++;
        now+=a[i].t1;
        a[i].flg=1;
        Q.push(a[i]);
    }
    else{
        Node e=Q.top();
        if(a[i].t1>e.t1)continue;
        Q.pop();
        now+=a[i].t1-e.t1;
        a[i].flg=1;
        Q.push(a[i]);
    }
}
printf("%d\n",ans);
return 0;
}

我是专业做水题的。

#include<cstdio>

long long n,m;

long long ksm(long long a,long long b){
long long base=a%100003,ans=1;
while(b){
    if(b%2)ans=(ans*base)%100003;
    base=(base*base)%100003;
    b/=2;
}
return ans;
}

int main(){
freopen("1008.in","r",stdin);
freopen("1008.out","w",stdout);
scanf("%lld %lld",&m,&n);
long long df=(ksm(m,n)-m*ksm(m-1,n-1))%100003;
printf("%lld\n",df<0?df+100003:df);
return 0;
}

前几天ygp就说了，是dp+spfa，然而我居然难以理解……

看着神犇们速A这题，我不禁感到太弱了……

#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
int en,n,m,K,E,d[105],h[105],D[105],P,dis[105][105],f[105],dp[105];

struct Edge{
int b,v,next;
}e[40005];

struct Closed{
int p,a,b;
}close[105];

void Yuchuli(int day1,int day2){
    memset(d,0,sizeof(d));
for(int i=0;i<P;i++){
    if(close[i].a>day2 || close[i].b<day1)continue;
    d[close[i].p]=1;
}
}

int spfa(){
memset(f,0,sizeof(f));
memset(D,0x3f,sizeof(D));
queue<int> Q;
Q.push(1);
f[1]=1;
D[1]=0;
int u,v;
while(!Q.empty()){
    u=Q.front();
    Q.pop();
    f[u]=0;
    for(int i=h[u];i;i=e[i].next){
        v=e[i].b;
        if(d[v])continue;
        if(D[u]+e[i].v<D[v]){
            D[v]=D[u]+e[i].v;
            if(!f[v]){
                Q.push(v);
                f[v]=1;
            }
        }
    }
}
return D[m];
}

void add(int sa,int sb,int sc){
e[++en].b=sb;
e[en].v=sc;
e[en].next=h[sa];
h[sa]=en;
}

int main(){
freopen("1003.in","r",stdin);
freopen("1003.out","w",stdout);
scanf("%d %d %d %d",&n,&m,&K,&E);
for(int i=0;i<E;i++){
    int sa,sb,sc;
    scanf("%d %d %d",&sa,&sb,&sc);
    add(sa,sb,sc);
    add(sb,sa,sc);
}
scanf("%d",&P);
for(int i=0;i<P;i++){
    scanf("%d %d %d",&close[i].p,&close[i].a,&close[i].b);
}
for(int i=1;i<=n;i++){
    for(int j=i;j<=n;j++){
        Yuchuli(i,j);
        dis[i][j]=spfa();
        if(dis[i][j]<0x3f3f3f3f)dis[i][j]*=j-i+1;
        //printf("%d\n",dis[i][j]);
    }
}
memset(dp,0x3f,sizeof(dp));
dp[0]=0;
for(int i=1;i<=n;i++){
    for(int j=0;j<i;j++){
        dp[i]=min(dp[i],dp[j]+dis[j+1][i]+K);
    }
}
printf("%d\n",dp[n]-K);
return 0;
}

水平若，代码丑，速度慢，这就是3个特点。

orz wyx秒杀这题