Wannafly模拟赛3 题解

首先大赞Wannafly啊，无私奉献啊有木有。我把我做出来的和补的题写个题解。

题目描述
一只南美洲亚马孙河流域热带雨林中的蝴蝶，偶尔扇动几下翅膀，可
以在两周以后引起美国德克萨斯州的一场龙卷风。――蝴蝶效应
由于这个理论的存在，大多数人认为将未来的事物送回过去将会引发
严重的时间悖论，但事实上还存在另外一套理论。
自然会对这类不和谐的蝴蝶效应做出调整，具体地来说就是触发一些
小概率的恶性事件来抹杀穿越者来消除其对未来的影响。
虽然听上去很荒诞，但Alicebell决定去验证这一假说，她将按1 ∼ n的
顺序依次到访过去的n个时间点。
这n个时间点各有一个能源参数

第一行，一个正整数n。
第二行，n个正整数

输出描述:

一行，一个正整数，最初需要携带能量下限。

示例1
输入

5
1 2 5 4 2

输出

备注:

对于30%的数据，n,

解法：水题。。维护i+A[i]的最大值。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL n,a[100010];

int main(){
    scanf("%lld",&n);
    for(int i=1; i<=n; i++) scanf("%lld", &a[i]);
    LL ans = -1;
    for(int i=1; i<=n; i++){
        ans = max(ans, a[i]+i-1);
    }
    printf("%lld\n", ans);
    return 0;
}

题目描述
贝伦卡斯泰露，某种程度上也可以称为古手梨花，能够创造几率近乎
为0的奇迹，通过无限轮回成功打破了世界线收束理论。
和某民科学者不同，贝伦并不在意世界线收束的那套理论，作为奇迹
之魔女，贝伦的爱好只在于品茶。
作为品茶的消遣，贝伦正在解一道简单的谜题。
给出一个长度为n的数列

第一行，一个正整数T，表示数据组数。
接下来T组数据，每组数据的第一行，一个正整数n，第二行n个正整数

输出描述:

每组数据输出一行，如果可以完成，输出Frederica Bernkastel，否则输出Furude Rika。

示例1
输入

3
4
1 1 2 2
6
1 2 3 4 5 6
4
1 2 2 1

输出

Frederica Bernkastel
Furude Rika
Furude Rika

备注:

对于30%的数据，n ≤ 16。
对于另20%的数据，T = 1。
对于另20%的数据，T = 2。
对于100%的数据，T ≤ 5，1 ≤

解法：爆搜，正解为折半枚举+Hash。

#include <bits/stdc++.h>
using namespace std;
int n,a1[44],a2[44],num[44];
bool dfs(int p1,int p2,int dep){
    if(p1>n/2||p2>n/2) return false;
    if(dep==n+1) return true;
    if(num[dep]==a1[p2+1]){
        a2[p2+1]=num[dep];
        bool flag = dfs(p1,p2+1,dep+1);
        if(flag) return true;
    }
    a1[p1+1]=num[dep];
    return dfs(p1+1,p2,dep+1);
}
int main(){
    int T;
    scanf("%d", &T);
    while(T--){
        scanf("%d", &n);
        for(int i=1; i<=n; i++) scanf("%d", &num[i]);
        a1[1] = num[1];
        bool flag = dfs(1, 0, 2);
        if(flag) puts("Frederica Bernkastel");
        else puts("Furude Rika");
    }
    return 0;
}

题目链接：https://www.nowcoder.com/acm/contest/13/D
解法：统计每个点的度数，按照图的形态统计属于哪种。

#include <bits/stdc++.h>
using namespace std;
int n,m,du[505];
map<int,int>mp;
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        du[u]++;
        du[v]++;
    }
    for(int i=1; i<=n; i++){
        mp[du[i]]++;
    }
    if(mp[4]==1&&mp[1]+mp[2]+mp[4]==n){
        puts("X");
    }else if(mp[3]==1&&mp[2]+mp[1]+mp[3]==n){
        puts("Y");
    }else if(mp[1]+mp[2]==n&&mp[1]!=0){
        puts("I");
    }else{
        puts("NotValid");
    }
    return 0;
}

题目链接：https://www.nowcoder.com/acm/contest/13/E
解法：离散化后直接用vector维护每个数在的位置，维护距离差值的前缀和，然后枚举二分，复杂度O(nlogn)，可以直接用tp,可以做到O（n）

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
int n, k, c[maxn];
unordered_map<int,int>mp;
vector<int>v[maxn];
int main(){
    scanf("%d%d",&n,&k);
    for(int i=1; i<=n; i++) scanf("%d", &c[i]);
    int dfsclk = 0;
    for(int i=1; i<=n; i++){
        if(!mp[c[i]]) mp[c[i]]=++dfsclk;
    }
    for(int i=1; i<=n; i++){
        v[mp[c[i]]].push_back(i);
    }
    int ans = 1;
    for(int i=0; i<maxn; i++){
        if(v[i].size()==0) continue;
        int sz = v[i].size();
        vector <int> tmp;
        tmp.push_back(0);
        for(int j=1; j<sz; j++) tmp.push_back(v[i][j]-v[i][j-1]-1);
        for(int j=1; j<sz; j++) tmp[j] += tmp[j-1];
        for(int j=0; j<sz; j++){
            int pos = upper_bound(tmp.begin(),tmp.end(),tmp[j]+k)-tmp.begin();
            pos--;
            ans = max(ans, pos-j+1);
        }
    }
    printf("%d\n", ans);
    return 0;
}

题目链接：https://www.nowcoder.com/acm/contest/13/F
解法：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+10;
int n, m, ans;
struct node{
    int l,r,sum;
}Tree[maxn<<2];
struct node2{
    int l,r,k;
    bool operator<(const node2 &rhs)const{
        return r<rhs.r;
    }
}a[maxn];
void pushup(int rt){
    Tree[rt].sum = Tree[rt*2].sum+Tree[rt*2+1].sum;
}
void build(int l,int r,int rt){
    Tree[rt].l=l,Tree[rt].r=r,Tree[rt].sum=0;
    if(l==r) return;
    int mid=(l+r)/2;
    build(l,mid,rt*2);
    build(mid+1,r,rt*2+1);
    pushup(rt);
}
void update(int pos, int rt){
    if(Tree[rt].l==Tree[rt].r){
        Tree[rt].sum=1;
        return;
    }
    int mid=(Tree[rt].l+Tree[rt].r)/2;
    if(pos<=mid) update(pos, rt*2);
    else update(pos, rt*2+1);
    pushup(rt);
}
int query(int L, int R, int rt){
    if(L<=Tree[rt].l&&Tree[rt].r<=R){
        return Tree[rt].sum;
    }
    int mid=(Tree[rt].l+Tree[rt].r)/2;
    int ret = 0;
    if(L<=mid) ret += query(L,R,rt*2);
    if(mid<R) ret += query(L,R,rt*2+1);
    return ret;
}
bool vis[maxn];

int main(){
    scanf("%d%d",&n,&m);
    for(int i=0; i<m; i++){
        scanf("%d%d%d", &a[i].l,&a[i].r,&a[i].k);
    }
    build(1, n, 1);
    sort(a,a+m);
    int t,cur;
    ans=0;
    for(int i=0; i<m; i++){
        t=query(a[i].l,a[i].r,1);
        cur=a[i].r;
        while(t<a[i].k){
            while(vis[cur]){--cur;}
            update(cur,1);
            ++t;
            ++ans;
            vis[cur]=1;
        }
    }
    printf("%d\n", ans);
    return 0;
}