Lvat_s Blog

新知识get:模拟退火

设置一个温度T，T越小越不随机

然后做个几万遍就可以了。

#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
 
double ans=2147483647,average=0;
int n,m,a[10005],sum[10005],zu[10005];
 
void Fire(){
double T=10000,nowans=0;
memset(sum,0,sizeof(sum));
for(int i=1;i<=n;i++){
    zu[i]=rand()%m+1;
    sum[zu[i]]+=a[i];
}
for(int i=1;i<=m;i++){
    nowans+=(sum[i]-average)*(sum[i]-average);
}
while(T>0.1){
    T*=0.9;
    int Nx,Ny,R=rand()%n+1;
    Nx=zu[R];
    if(T>500){
        int sa=2147483647,sb;
        for(int i=1;i<=m;i++){
            if(sa>sum[i]){
                sa=sum[i];
                sb=i;
            }
        }
        Ny=sb;
    }
    else Ny=rand()%m+1;
    if(Nx==Ny)continue;
    double lastans=nowans;
    nowans-=(sum[Nx]-average)*(sum[Nx]-average);
    nowans-=(sum[Ny]-average)*(sum[Ny]-average);
    sum[Nx]-=a[R];
    sum[Ny]+=a[R];
    nowans+=(sum[Nx]-average)*(sum[Nx]-average);
    nowans+=(sum[Ny]-average)*(sum[Ny]-average);
    if(nowans<=lastans){zu[R]=Ny;}
    else {
        if(rand()%10000>T){
            sum[Nx]+=a[R];
            sum[Ny]-=a[R];
            nowans=lastans;
        }
        else {
            zu[R]=Ny;
        }
    }
}
ans=min(nowans,ans);
}
 
int main(){
srand(19990720);
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){
    scanf("%d",&a[i]);
    average+=a[i];
}
average/=m;
for(int i=1;i<=10000;i++){
    Fire();
}
printf("%.2lf\n",sqrt(ans/m));
return 0;
}

公式: f[i]=3*f[i-1]-f[i-2]+2

我自己是用了三个变量滚动。需要写一个高精度。

#include<cstdio>
#include<cstring>
 
struct Num{
int n,s[100005];
}f1,f2,f3;
 
int n;
 
void Do(){
f3.n=f2.n;
memset(f3.s,0,sizeof(f3.s));
for(int i=0;i<f2.n;i++){
    f3.s[i]+=f2.s[i]*3;
    if(f3.s[i]>9){
        f3.s[i+1]+=f3.s[i]/10;
        f3.s[i]%=10;
    }
}
if(f3.s[f3.n]>0)f3.n++;
//printf("CTest2:%d%d\n",f2.s[0],f2.s[1]);
//printf("CTest3:%d%d\n",f3.s[0],f3.s[1]);
//printf("Test1:%d%d\n",f1.s[0],f1.s[1]);
f3.s[0]+=2-f1.s[0];
//printf("Test3:%d%d\n",f3.s[0],f3.s[1]);
if(f3.s[0]>9){
    f3.s[1]+=f3.s[0]/10;
    //printf("Test:%d%d\n",f3.s[0],f3.s[1]);
    f3.s[0]%=10;
}
else if(f3.s[0]<0){
    f3.s[1]--;
    f3.s[0]+=10;
}
for(int i=1;i<f1.n;i++){
    f3.s[i]-=f1.s[i];
    if(f3.s[i]<0){
        f3.s[i+1]--;
        f3.s[i]+=10;
    }
}
if(f3.s[f3.n-1]==0)f3.n--;
}
 
void Copy(){
f1.n=f2.n;
for(int i=0;i<f2.n;i++){f1.s[i]=f2.s[i];}
f2.n=f3.n;
for(int i=0;i<f3.n;i++){f2.s[i]=f3.s[i];}
}
 
int main(){
freopen("1002.in","r",stdin);
freopen("1002.out","w",stdout);
scanf("%d",&n);
if(n==1){printf("1\n");return 0;}
if(n==2){printf("5\n");return 0;}
f1.n=1;
f1.s[0]=1;
f2.n=1;
f2.s[0]=5;
n-=2;
while(n--){
    Do();
    Copy();
}
for(int i=f2.n-1;i>=0;i--){
    printf("%d",f2.s[i]);
}
putchar('\n');
return 0;
}

据说网络流写得好也能过……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秒杀这题