喵哈哈村的四月半活动（一）

题解：

唯一的case，就是两边长度一样的时候，第三边只有一种情况。

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <algorithm>

#include <cstring>

#include <queue>

#include <vector>

#include <map>

#include <cmath>

#define INF 1000000000

using namespace std;

const int MOD = 1234567;

int x,y;

int main()

{

    scanf("%d%d",&x,&y);

    double ans;

    if(x!=y)

    {

        if(x<y)

            swap(x,y);

        ans=sqrt(x*x-y*y);

        printf("%.10f\n",ans);

    }

    ans=sqrt(x*x+y*y);

    printf("%.10f\n",ans);

    return 0;

}

喵哈哈村的四月半活动（二）

题解：拿一个map或者一个set，来统计这个数是否出现过即可。

#include<bits/stdc++.h>

using namespace std;

set<int> S;

int main(){

    int n;

    scanf("%d",&n);

    for(int i=0;i<n;i++){

        int p;

        scanf("%d",&p);

        if(S.find(p)!=S.end()){

            cout<<"1";

        }else{

            cout<<"0";

        }

        S.insert(p);

    }

    cout<<endl;

}

喵哈哈村的四月半活动（三）

题解：转换一下题意，实际上就是问你从（x,y）到(1,1)的最短路是多少。

这个直接写个spfa就好了。

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <algorithm>

#include <cstring>

#include <queue>

#include <vector>

#include <map>

#include <cmath>

#define INF 1000000000

using namespace std;

const int M = 510;

struct node

{

    int x,y;

}q[M*M*10];

int n,m,n1,m1;

int dx[5]={0,-1,0,1,0};

int dy[5]={0,0,1,0,-1};

int a[M][M],dis[M][M],flag[M][M];

void bfs(int x,int y)

{

    for(int i=1;i<=n;i++)

        for(int j=1;j<=m;j++)

            dis[i][j]=INF;

    dis[x][y]=0;

    int l=0,r=0;

    q[++r].x=x;

    q[r].y=y;

    flag[x][y]=1;

    while(l!=r)

    {

        l++;

        if(l>100010)

            l=1;

        node k=q[l];

        flag[k.x][k.y]=0;

        for(int i=1;i<=4;i++)

        {

            node k1;

            k1.x=k.x+dx[i];

            k1.y=k.y+dy[i];

            if(k1.x>=1&&k1.x<=n&&k1.y>=1&&k1.y<=m)

            {

                if(dis[k1.x][k1.y]>dis[k.x][k.y]+a[k1.x][k1.y]&&a[k1.x][k1.y]!=0)

                {

                    dis[k1.x][k1.y]=dis[k.x][k.y]+a[k1.x][k1.y];

                    if(!flag[k1.x][k1.y])

                    {

                        flag[k1.x][k1.y]=1;

                        r++;

                        if(r>100010)

                            r=1;

                        q[r]=k1;

                    }

                }

            }

        }

    }

}

int main()

{

    scanf("%d%d%d%d",&n,&m,&n1,&m1);

    for(int i=1;i<=n;i++)

        for(int j=1;j<=m;j++)

            scanf("%d",&a[i][j]);

    bfs(n1,m1);

    if(dis[1][1]==INF||a[1][1]==0)

    {

        printf("-1\n");

        return 0;

    }

    printf("%d\n",dis[1][1]);

    return 0;

}

喵哈哈村的四月半活动(四)

题解：dp[i][j]表示当前还有i个节点，节点权值和为j的方案数是多少。

然后转移就好了。

#include<stdio.h>

#include<iostream>

#include<algorithm>

#include<string.h>

#include<bitset>

#define MOD 10007

#define N 1010

#define M 1010

#define INF (1<<30)

using namespace std;

int n,m;

int mem[N][M];

int dp(int index,int val){

    if(index==1 && val>0) return 1;

    int tmp=0;

    for(int i=1;i<=val-index+1;i++){

        if(mem[index-1][val-i]==-1) mem[index-1][val-i]=dp(index-1,val-i);

        tmp=(tmp+mem[index-1][val-i])%MOD;

    }

    return tmp;

}

int main(){

    scanf("%d%d",&n,&m);

    memset(mem,-1,sizeof(mem));

    printf("%d",dp((m+1)/2,n));

    return 0;

}

喵哈哈村的四月半活动（五）

题解：暴力大模拟就好了。。。

#include<stdio.h>

#include<iostream>

#include<algorithm>

#include<string.h>

#include<bitset>

#define INF (1<<30)

#define LEN 1010

#define L 1010

using namespace std;

char str[LEN];

char x[L];

char flag[1000];

char t[1000];

bool vis;

int main(){

    int n;

    scanf("%d",&n);

    vis=0;

    while(n--){

        if(vis) strcpy(flag,t);

        else scanf("%s",flag);

        if(strcmp(flag,"set")==0){

            scanf("%s",x);

            strcpy(str,x);

            vis=0;

    //		cout<<str<<endl;

            continue;

        }

        if(strcmp(flag,"add")==0){

            int a;

            scanf("%d%s",&a,x);

            char tmp[LEN];

            strcpy(tmp,str+a);

            strcpy(str+a,x);

            int len=strlen(x);

            strcpy(str+a+len,tmp);

            vis=0;

    //		cout<<str<<endl;

            continue;

        }

        if(strcmp(flag,"del")==0){

            int a;

            scanf("%d",&a);

            scanf("%s",t);

            char tmp[LEN];

            if(0<=t[0]-'0' && t[0]-'0'<=9){

                int len=strlen(t);

                int b=0;

                for(int i=0;i<len;i++) b=b*10+(t[i]-'0');

                if(a==b) {

                    vis=0;

                    continue;

                }

                if(a>b) swap(a,b);

                strcpy(tmp,str+b-1);

                strncpy(str,str,a);

                strcpy(str+a,tmp);

                vis=0;

        //		cout<<str<<endl;

                continue;

            }

            else {

                strcpy(tmp,str+a-1);

                strcpy(str,tmp);

                vis=1;

        //		cout<<str<<endl;

                continue;

            }

        }

        if(strcmp(flag,"rev")==0){

            reverse(str,str+strlen(str));

            vis=0;

        }

    //	cout<<str<<endl;

    }

    cout<<str<<endl;

    return 0;

}