又考交互题，凉心吗……由于一个题是交互题而直接跳过的是不是只剩下我了……

B. 小明的变换

进行多少次操作r都是不会变的，只有 复制一个和下一个相等的 和 认为当前数被移动了 两种情况，于是用两个指针从后往前匹配，如果当前位置一样匹配上一个，否则看自己的下一位能不能拉一个数到后面代替a匹配b，b的指针移动，还不行的话看看当前位置是不是可以被拉到后面，剩下的就不合法。

关于设个顺序，因为a[p1+1]==b[p2]是一个更不容易被满足的条件，而一个被后面取过的数可以在任意时刻被删掉，所以要先判断能不能拉数到后面。

code 

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 1e6 + 2;
const int nx = 5e5;

int T, n, a[maxn], b[maxn], cnt[maxn];

inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-')
        {
            f = -1;
        }
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        x = (x << 1) + (x << 3) + (ch^48);
        ch = getchar();
    }
    return x * f;
}

bool solve()
{
    for(int i=1; i<=nx; i++) cnt[i] = 0;
    int p1 = n, p2 = n;
    while(p1 >= 1 && p2 >= 1)
    {
        if(a[p1] == b[p2])
        {
            p1--; p2--; continue;
        }
        if(p1 < n && a[p1+1] == b[p2])
        {
            cnt[b[p2]]++; p2--; continue;
        }
        if(cnt[a[p1]])
        {
            cnt[a[p1]]--; p1--; continue;
        }
        return false;
    }
    return true;
}

int main()
{
    freopen("trans.in", "r", stdin);
    freopen("trans.out", "w", stdout);
    
    T = read();
    while(T--)
    {
        n = read();
        for(int i=1; i<=n; i++) a[i] = read();
        for(int i=1; i<=n; i++) b[i] = read();
        if(solve()) printf("YES\n");
        else printf("NO\n");
    }

    return 0;
}

 

C. 小明过生日

我大E了没有闪

要不是因为它改时间我就A了，第一版74那是因为还没写完(四个小时做一道题都不够？！我还是提高做题速度去吧)一听说考试结束的消息秒加freopen一遍过编译先交为快

越是会的东西越不想写，尤其是解释需要用到图……很多图……

code 
 #include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 1e5 + 2;

int n, m, cnt, now, ans[maxn], num, hp, id, id2;
typedef pair<int, int> pii;
pii p[maxn];
bool flag;

inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-')
        {
            f = -1;
        }
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        x = (x << 1) + (x << 3) + (ch^48);
        ch = getchar();
    }
    return x * f;
}

int main()
{
    freopen("birth.in", "r", stdin);
    freopen("birth.out", "w", stdout);
    
    n = read(); m = read();
    for(int i=1; i<=m; i++)
    {
        int x = read();
        if(x & 1)
        {
            num++; p[++cnt] = pii(1, x-1);
            if(!id) id = cnt;
            else id2 = cnt;
        }
        else p[++cnt] = pii(2, x-2);
    }
    if(num > 2)
    {
        printf("-1"); exit(0);
    }
    if(id && id2 && m == 2)
    {
        printf("%d %d\n", p[id].first+p[id].second, p[id2].first+p[id2].second);
        ans[++hp] = p[id].second + 2; ans[++hp] = p[id2].second;
        if(!ans[hp]) hp--;
        printf("%d\n", hp);
        for(int i=1; i<=hp; i++)
        {
            printf("%d ", ans[i]);
        }
        printf("\n");
        exit(0);
    }
    if(id2)
    {
        ans[++hp] = p[id2].first; ans[++hp] = p[id2].second;
        now++; flag = 1;
    }
    for(int i=1; i<=cnt; i++)
    {
        if(i == id || i == id2) continue;
        if(now == 0)
        {
            ans[++hp] = p[i].first; ans[++hp] = p[i].second;
            now++;
        }
        else if(now == 1 && !flag)
        {
            int r2 = ans[hp--], r1 = ans[hp--];
            ans[++hp] = 1; ans[++hp] = r2 + 2; ans[++hp] = 1; ans[++hp] = p[i].second;
            now++;
        }
        else 
        {
            int r2 = ans[hp--], r1 = ans[hp--];
            ans[++hp] = r2 + 2; ans[++hp] = 1; ans[++hp] = p[i].second;
            now++;
        }
    }
    if(id)
    {
        if(now == 0)
        {
            ans[++hp] = p[id].first; ans[++hp] = p[id].second;
        }
        else if(now == 1)
        {
            int r2 = ans[hp--], r1 = ans[hp--];
            ans[++hp] = 1; ans[++hp] = r2 + 2; ans[++hp] = p[id].second;
        }
        else 
        {
            int r2 = ans[hp--], r1 = ans[hp--];
            ans[++hp] = r2 + 2; ans[++hp] = p[id].second;
        }
    }
    if(id2) printf("%d ", p[id2].first + p[id2].second);
    for(int i=1; i<=cnt; i++)
    {
        if(i == id || i == id2) continue;
        printf("%d ", p[i].first + p[i].second);
    }
    if(id) printf("%d ", p[id].first + p[id].second);
    printf("\n");
    if(ans[hp] == 0) hp--;
    printf("%d\n", hp);
    for(int i=1; i<=hp; i++)
    {
        printf("%d ", ans[i]);
    }
    printf("\n");

    return 0;
}

原文地址：http://www.cnblogs.com/Catherine2006/p/16877280.html

1. 本站所有资源来源于用户上传和网络，如有侵权请邮件联系站长！ 2. 分享目的仅供大家学习和交流，请务用于商业用途! 3. 如果你也有好源码或者教程，可以到用户中心发布，分享有积分奖励和额外收入！ 4. 本站提供的源码、模板、插件等等其他资源，都不包含技术服务请大家谅解！ 5. 如有链接无法下载、失效或广告，请联系管理员处理！ 6. 本站资源售价只是赞助，收取费用仅维持本站的日常运营所需！ 7. 如遇到加密压缩包，默认解压密码为"gltf",如遇到无法解压的请联系管理员！ 8. 因为资源和程序源码均为可复制品，所以不支持任何理由的退款兑现，请斟酌后支付下载 声明：如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性