Lvat_s Blog

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

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

普通的最小生成树。

#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秒杀这题

作为一个刚刚开始学习C++的oier……首先要做的事就是orz学长们……wzf hsh nxy wlp lzz cjy xdm wyy等等……

然后要orz同级的神犇们wyx hyq lyz rky gqy cyd djch zwt dhp yyx等等……

还有初三大神MedalPluS……

我现在还是大蒟蒻……差的远呢……

从今天开始吧。