2018网易游戏盘古雷火笔试

1.大概题意是给定一串硬币，每次给一个区间进行翻面，最后求某个点是正面还是反面
用了前缀和
代码如下

#include <bits/stdc++.h>
#define rep(i,a,b) for (int i=a;i<b;i++)
using namespace std;
const int N=1e4+1111;
int a[N];
int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    rep(i,0,k)
    {
        int l,r;
        scanf("%d%d",&l,&r);
        a[l]++;
        a[r+1]--;
    }
    int tot = 0;
    for (int i=1;i<=n;i++)
    {
        tot += a[i];
        if (tot&1) putchar('1');
        else putchar('0');
    }
    puts("");
    return 0;
}

2.给三个点求插值
因为没学过插值。。不会计算插值gg
其余部分应该都是对的
T T
3.给一堆路 求最小连同路吧大概这意思 并查集裸过

#include <bits/stdc++.h>
#define rep(i,a,b) for (int i=a;i<b;i++)
using namespace std;
const int N=1e3;
int f[N],use[N];
void init(int n)
{
    rep(i,0,n+1)
        f[i]=i;
}
int rot(int x)
{
    while (x!=f[x]) x=f[x]=f[f[x]];
    return x;
}
void uni(int x,int y)
{
    f[rot(x)]=rot(y);
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    init(n);
    rep(i,0,m)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        uni(x,y);
    }
    rep(i,1,n+1)
    use[rot(i)]=1;
    int ans=-1;
    rep(i,1,n+1)
        ans+=use[i];
    printf("%d\n",ans);
    return 0;
}

4.染色问题 每次可以染一段 下次再在中间染再算一次 比如ABCBA 首先染上AAAAA 然后ABBBA 再然后ABCBA 共三次 明显的dp问题 用计算搜索写

#include <bits/stdc++.h>
#define rep(i,a,b) for (int i=a;i<b;i++)
using namespace std;
const int N=111;
char s[N];
int n;
int a[N],f[N][N][27];
int dfs(int l,int r,int col)
{
    if (l>r) return 0;
    if (l==r) return a[l] != col;
    if (f[l][r][col] != -1) return f[l][r][col];
    int ans=0x3f3f3f3f;
    rep(i,l,r+1)
    {
        ans=min(ans,dfs(l+1,i,a[l])+dfs(i+1,r,col)+(a[l]!=col));
    }
    return f[l][r][col]=ans;
}
int main()
{
    scanf("%s",s);
    n = strlen(s);
    rep(i,0,n) a[i] = s[i]-'A'+1;
    memset(f,-1,sizeof(f));
    cout<<dfs(0,n-1,0)<<endl;
    return 0;
}