Codeforces Round #449 (Div. 2)

A - Scarborough Fair

题意好理解.

View Code

//A. Scarborough Fair 字符更换
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
using namespace std;
const int N=1e5+10;
char s[N];
int main(){
    int n,m;
    while(~scanf("%d%d",&n,&m)){
        scanf("%s",s);
        int len=strlen(s);
        while(m--){
            char a,b;
            int l,r;
            cin>>l>>r>>a>>b;
            for(int i=l-1;i<r;i++){
                if(s[i]==a)s[i]=b;
            }
        }
        printf("%s\n",s);
    }
    return 0;
}

B - Chtholly’s request

题意：前K个长度为偶数的回文数相加%p；

思路：长度为偶数，那么每个数对称一下都是符合要求的回文数

AC代码：

思维

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<queue>
using namespace std;
int k,p;
long long zcy[100005];
void init()
{
    int cnt=0;
    for(int i=1;i<=100000;i++)
    {
        long long tmp=i;
        int p=i;
        while(p){
            tmp=tmp*10+p%10;
            p/=10;
        }
        zcy[++cnt]=tmp;
    }
}
int main()
{
    init();
    while(~scanf("%d%d",&k,&p))
    {
        long long sum=0;
        for(int i=1;i<=k;i++){
            sum+=zcy[i];
            sum%=p;
        }
        printf("%lld\n",sum);
    }
    return 0;
}

思维

C - Nephren gives a riddle

递归，模拟

View Code

/*
http://codeforces.com/contest/897/problem/C
*/
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define LL long long
using namespace std;
inline LL read();
const int MAXN = 1e5+10;
 
string s0 = "What are you doing at the end of the world? Are you busy? Will you save us?",
s1 = "What are you doing while sending \"",s2 = "\"? Are you busy? Will you send \"",s3 = "\"?";
 
LL len[MAXN];
LL len0 = s0.size(),len1 = s1.size(),len2 = s2.size(),len3 = s3.size();
 
char fun(LL n,LL k)
{
    if(!n)
    {
        if(k <= len0)
            return s0[k-1];
        else
            return '.';
    }
    if(k <= len1)
        return s1[k-1];
    k -= len1;
    if(k <= len[n-1] || !len[n-1])
        return fun(n-1,k);
    k -= len[n-1];
    if(k <= len2)
        return s2[k-1];
    k -= len2;
    if(k <= len[n-1] || !len[n-1])
        return fun(n-1,k);
    k -= len[n-1];
    if(k <= len3)
        return s3[k-1];
    return '.';
}
 
int main(void)
{
    int q = read();
    len[0] = len0;
    LL tmp = len1+len2+len3;
    for(int i = 1;len[i-1] <= 1e18; ++i)
    {
        len[i] = 2*len[i-1]+tmp;
    }
    while(q--)
    {
        LL n = read(),k = read();
        putchar(fun(n,k));
    }
}
 
inline LL read()
{
    LL 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*10+ch-'0';ch=getchar();}
    return x*f;
}

D - Ithea Plays With Chtholly

交互

所以应该能想到从两边，开始扫描，让大于c/2的从n开始往下扫描，这样刚刚那组数据就可以过了，复杂度正好是n*c/2。

View Code

#include <bits/stdc++.h>
using namespace std;
int n;
int a[1005];
int judge()
{
    for(int i=1; i<=n; i++)
    {
        if(a[i]==0)return 0;
        if(i<n && a[i]>a[i+1])return 0;
    }
    return 1;
}
int main()
{
    int m, i, j, c;
    cin>>n>>m>>c;
    for(i=1; i<=m; i++)
    {
        int x;
        scanf("%d", &x);
        if(x<=c/2)
        {
            for(int i=1; i<=n; i++)
            {
                if(a[i]==0 || a[i]>x)
                {
                    a[i]=x;
                    cout<<i<<endl;
                    break;
                }
            }
        }
        else 
        {
            for(int i=n; i>=1; i--)
            {
                if(a[i]==0 || a[i]<x)
                {
                    a[i]=x;
                    cout<<i<<endl;
                    break;
                }
            }
        }
        if(judge())return 0;
    }
    return 0;
}

E - Willem, Chtholly and Seniorious

珂朵莉树模板题。

以下给出些链接

一

二

三

四

View Code

#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<cstring>
#include<cstdio>
#include<set>
using namespace std;
typedef long long lt;
#define IT set<node>::iterator
#define pir pair<lt,int>
#define mkp(x,y) make_pair(x,y)

lt read()
{
    lt f=1,x=0;
    char ss=getchar();
    while(ss<'0'||ss>'9'){if(ss=='-')f=-1;ss=getchar();}
    while(ss>='0'&&ss<='9'){x=x*10+ss-'0';ss=getchar();}
    return f*x;
}

lt seed,vmax;
lt rnd()
{
    lt res=seed;
    seed=(seed*7+13)%1000000007;
    return res;
}

const int maxn=100010;
int n,m;
lt a[maxn];
struct node
{
    int ll,rr;
    mutable lt val;
    node(int L,int R=-1,lt V=0): ll(L), rr(R), val(V) {}
    bool operator < (const node& tt)const { return ll<tt.ll;}
};
set<node> st;

lt qpow(lt a,lt k,lt p)
{
    lt res=1; a%=p;
    while(k>0){
        if(k&1) res=(res*a)%p;
        a=(a*a)%p; k>>=1;
    }
    return res;
}

IT split(int pos)
{
    IT it=st.lower_bound(node(pos));
    if(it!=st.end()&&it->ll==pos) return it;
    --it;
    int ll=it->ll,rr=it->rr;
    lt val=it->val;
    st.erase(it);
    st.insert(node(ll,pos-1,val));
    return st.insert(node(pos,rr,val)).first;
}

void assign(int ll,int rr,lt val)
{
    IT itr=split(rr+1),itl=split(ll);
    st.erase(itl,itr);
    st.insert(node(ll,rr,val));
}

void add(int ll,int rr,lt val)
{
    IT itr=split(rr+1),itl=split(ll);
    for(;itl!=itr;++itl) itl->val+=val;
}

lt kth(int ll,int rr,int k)
{
    vector<pir> vec;
    IT itr=split(rr+1),itl=split(ll);
    for(;itl!=itr;++itl)
    vec.push_back(pir(itl->val,itl->rr-itl->ll+1));
    sort(vec.begin(),vec.end());
    for(vector<pir>::iterator it=vec.begin();it!=vec.end();++it)
    {
        k-=it->second;
        if(k<=0) return it->first;
    }
    return -1;
}

lt qsum(int ll,int rr,lt x,lt y)
{
    lt res=0;
    IT itr=split(rr+1),itl=split(ll);
    for(;itl!=itr;++itl)
    res+=(qpow(itl->val,x,y)*((itl->rr-itl->ll+1)%y))%y,res%=y;
    return res;
}

int main()
{
    n=read();m=read();
    seed=read();vmax=read();
    
    for(int i=1;i<=n;++i)
    {
        a[i]=(rnd()%vmax)+1;
        st.insert(node(i,i,a[i]));
    }
    
    for(int i=1;i<=m;++i)
    {
        int op=(rnd()%4)+1;
        int ll=(rnd()%n)+1,rr=(rnd()%n)+1;
        lt x,y;

        if(ll>rr) swap(ll,rr);
        if(op==3) x=(rnd()%(rr-ll+1))+1;
        else x=(rnd()%vmax)+1;
        if(op==4) y=(rnd()%vmax)+1;
        
        if(op==1) add(ll,rr,x);
        else if(op==2) assign(ll,rr,x);
        else if(op==3) printf("%lld\n",kth(ll,rr,x));
        else if(op==4) printf("%lld\n",qsum(ll,rr,x,y));
    }
    return 0;
}

概率随机+set

2. 题意描述
   有一个序列a[]a[],长度为nn。然后是mm次操作。
   操作1：将al,al+1,…,aral,al+1,…,ar的数,全部加上xx;
   操作2：将al,al+1,…,aral,al+1,…,ar的数,全部置位xx;
   操作3：求al,al+1,…,aral,al+1,…,ar的数中的第xx小的数;
   操作4：求(∑ri=laxi)%y(∑i=lraix)%y;
   注意：序列a[]a[]，以及所有操作（即op,l,r,x,yop,l,r,x,y）都是等概率的随机生成的。

数据范围：
1 ≤ n, m ≤ 105, 0 ≤ seed < 109 + 7, 1 ≤ vmax ≤ 1091 ≤ n, m ≤ 105, 0 ≤ seed < 109 + 7, 1 ≤ vmax ≤ 109
3. 解题思路
上面四种操作，出现的概率都是1414。
假如用线段来描述序列a[]a[]中值相同的子序列。当n=105n=105时，初始的时候，序列a[]a[]随机分布，所以线段很很多。但是经过多次操作2之后，会让这个序列极速收敛，最终收敛到小于5050左右。然而概率论太差，我并不会证明合并到线段数目小于某一个值的次数的数学期望。
但是自己打印了一下，大概250250次合并就能让线段数目小于200。
然后，知道了这种性质之后，就可以用setset来保存维护线段。剩下的操作就是暴力删除一堆线段，暴力插入一些线段，暴力对线段进行查询。

View Code

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int inf = 0x3f3f3f3f;
const ll infl = 0x3f3f3f3f3f3f3f3fLL;
template<typename T> inline void umax(T &a, T b) { a = max(a, b); }
template<typename T> inline void umin(T &a, T b) { a = min(a, b); }
void debug() { cout << endl; }
template<typename T, typename ...R> void debug (T f, R ...r) { cout << "[" << f << "]"; debug (r...); }

const int MAXN = 100005;

ll n, m, seed, vmax, a[MAXN];

ll rnd() {
    ll ret = seed;
    seed = (seed * 7 + 13) % 1000000007;
    return ret;
}

struct Line {
    pii itv; ll val;
    Line() {}
    Line(pii itv, ll val) : itv(itv), val(val) {}
    bool operator < (const Line& line) const {
        return itv < line.itv;
    }
};

bool cmp_val(const Line& l1, const Line& l2)  {
    return l1.val < l2.val;
}

set<Line> st;
set<Line>::iterator it, it1, it2;
void oper1(int l, int r, ll x) {
    // [it1, it2)
    it1 = st.upper_bound(Line(pii(l, inf), 0ll)); --it1;
    it2 = st.upper_bound(Line(pii(r, inf), 0ll));
    vector<Line> buf;
    for (it = it1; it != it2; ++it) {
        if ((it->itv).first > r) break;
        buf.push_back(*it);
    }
    st.erase(it1, it2);
    if (buf[0].itv.first < l) {
        st.insert(Line(pii(buf[0].itv.first, l - 1), buf[0].val));
        buf[0].itv.first = l;
    }
    int sz = buf.size();
    if (buf[sz - 1].itv.second > r) {
        st.insert(Line(pii(r + 1, buf[sz - 1].itv.second), buf[sz - 1].val));
        buf[sz - 1].itv.second = r;
    }
    for (Line& line : buf) {
        line.val += x;
        st.insert(line);
    }
    // for(int i = l; i <= r; ++i) a[i] += x;
}

void oper2(int l, int r, ll x) {
    // [it1, it2)
    it1 = st.upper_bound(Line(pii(l, inf), 0ll)); --it1;
    it2 = st.upper_bound(Line(pii(r, inf), 0ll));
    vector<Line> buf;
    for (it = it1; it != it2; ++it) {
        if ((it->itv).first > r) break;
        buf.push_back(*it);
    }
    st.erase(it1, it2);
    if (buf[0].itv.first < l && buf[0].val != x) {
        st.insert(Line(pii(buf[0].itv.first, l - 1), buf[0].val));
        buf[0].itv.first = l;
    }
    int sz = buf.size();
    if (buf[sz - 1].itv.second > r && buf[sz - 1].val != x) {
        st.insert(Line(pii(r + 1, buf[sz - 1].itv.second), buf[sz - 1].val));
        buf[sz - 1].itv.second = r;
    }
    st.insert(Line(pii(buf[0].itv.first, buf[sz - 1].itv.second), x));
    // for(int i = l; i <= r; ++i) a[i] = x;
}

ll oper3(int l, int r, ll x) {
    // [it1, it2)
    it1 = st.upper_bound(Line(pii(l, inf), 0ll)); --it1;
    it2 = st.upper_bound(Line(pii(r, inf), 0ll));
    vector<Line> buf;
    for (it = it1; it != it2; ++it) {
        if ((it->itv).first > r) break;
        buf.push_back(*it);
    }
    if (buf[0].itv.first < l) {
        buf[0].itv.first = l;
    }
    int sz = buf.size();
    if (buf[sz - 1].itv.second > r) {
        buf[sz - 1].itv.second = r;
    }
    sort(buf.begin(), buf.end(), cmp_val);
    ll w = 0;
    for (Line& line : buf) {
        w += (line.itv.second - line.itv.first + 1);
        if (w >= x) return line.val;
    }
    return -1;
}

ll qpow(ll a, ll b, ll mod) {
    ll ret = 1;
    a = a % mod;    // notice here!!!
    while (b > 0) {
        if (b & 1) ret = ret * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ret;
}

ll oper4(int l, int r, ll x, ll y) {
    // [it1, it2)
    it1 = st.upper_bound(Line(pii(l, inf), 0ll)); --it1;
    it2 = st.upper_bound(Line(pii(r, inf), 0ll));
    vector<Line> buf;
    for (it = it1; it != it2; ++it) {
        if ((it->itv).first > r) break;
        buf.push_back(*it);
    }
    if (buf[0].itv.first < l) {
        buf[0].itv.first = l;
    }
    int sz = buf.size();
    if (buf[sz - 1].itv.second > r) {
        buf[sz - 1].itv.second = r;
    }

    ll ret = 0;
    for (Line& line : buf) {
        int w = (line.itv.second - line.itv.first + 1);
        ret += (ll)w * qpow(line.val, x, y) % y;
        ret %= y;
    }
    return ret;
}

int main() {
#ifdef ___LOCAL_WONZY___
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w+", stdout);
#endif // ___LOCAL_WONZY___
    cin >> n >> m >> seed >> vmax;
    for (int i = 1; i <= n; ++i) a[i] = (rnd() % vmax) + 1;
    st.clear();
    for (int i = 1; i <= n; ++i) {
        int j = i;
        while (j + 1 <= n && a[i] == a[j + 1]) ++j;
        st.insert(Line(pii(i, j), a[i]));
        i = j;
    }

    int op, l, r; ll x, y;
    int cnt = 0;
    for (int i = 1; i <= m; ++i) {
        op = rnd() % 4 + 1;
        l = rnd() % n + 1;
        r = rnd() % n + 1;
        if (l > r) swap(l, r);
        if (op == 3) x = (rnd() % (r - l + 1)) + 1;
        else x = (rnd() % vmax) + 1;
        if (op == 4) y = (rnd() % vmax) + 1;

        // debug(op, l, r, x, y);

        if (op == 1) oper1(l, r, x);
        else if (op == 2) oper2(l, r, x);
        else if (op == 3) {
            ll ret = oper3(l, r, x);
            cout << ret << endl;
        } else {
            ll ret = oper4(l, r, x, y);
            cout << ret << endl;
        }
    }
#ifdef ___LOCAL_WONZY___
    cout << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC * 1000 << "ms." << endl;
#endif // ___LOCAL_WONZY___
    return 0;
}