RA.Raksasa’s A+B

签到题，long long的a+b，直接计算。

RB.大连大学，我心中的挚爱

以下是出题组想到的所有名词，输出任意一个即可通过，可能不全面，但我校校歌里面一定有“大连大学”四个字这一点毋庸置疑。

RC.迁徙行

本题用于学习使用提问功能。

RD.勇敢一点

从矩阵中找到1，然后输出下标即可。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
char a[N][N];
int main()
{
    ll n,m;
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%s",a[i]+1);
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(a[i][j]=='1')
            {
                printf("%d %d",i,j);
                return 0;
            }
        }
    }
    return 0;
}

RE.永恒是什么？

本次比赛最难的题之一，有三种解法：暴力区间合并，动态开点线段树，线段树离散化。
暴力区间合并(主要考察stl库的综合应用)：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll a[N];
int main()
{
    ll n,m;
    scanf("%lld%lld",&n,&m);
    map<ll,ll> ma;
    map<ll,ll>::iterator itl,itr,it;
    while(m--)
    {
        ll op,l,r;
        scanf("%lld%lld%lld",&op,&l,&r);
        if(op==1)
        {
            bool bl=1;
            while(bl)
            {
                bl=0;
                r=max(r,ma[l]);
                ma[l]=r;
                it=ma.lower_bound(l);
                if(it!=ma.begin())
                {
                    itl=prev(it);
                    if(itl->second>=l)
                    {
                        l=itl->first;
                        r=max(itl->second,r);
                        ma.erase(itl);
                        bl=1;
                    }
                }
                itr=next(it);
                if(itr!=ma.end())
                {
                    if(itr->first<=r)
                    {
                        r=max(itr->second,r);
                        ma.erase(itr);
                        bl=1;
                    }
                }
                ma.erase(it);
                ma[l]=r;
            }
        }
        else
        {
            it=ma.upper_bound(l);
            if(it==ma.begin())
            {
                printf("NO\n");
                continue;
            }
            it--;
            if(it->second>=r)
            {
                printf("YES\n");
            }
            else
            {
                printf("NO\n");
            }
        }
    }
    return 0;
}

动态开点线段树：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
struct tree {
    int add;
    int sum;
    int l, r;
#define sum(x) tree[x].sum
#define add(x) tree[x].add
#define l(x) tree[x].l
#define r(x) tree[x].r
}tree[100005<<6];
ll top = 1;
void pushdown(ll p, ll len) {
    if (len <= 1) return;
    if (!l(p)) l(p) = ++top;
    if (!r(p)) r(p) = ++top;
    if(add(p)){
        sum(l(p)) = add(p);
        add(l(p)) = add(p);
        sum(r(p)) = add(p);
        add(r(p)) = add(p);
        add(p) = 0;
    }
}
ll getsum(ll l, ll r, ll p = 1, ll s = 1, ll t = 1e9+2) {
    // [l,r] 为查找区间,[s,t] 为当前区间
    if (s >= l && t <= r) return sum(p);
    pushdown(p, t - s + 1);
    ll mid = (s + t ) / 2, re = 1;
    if (mid >= l) re = getsum(l, r, l(p), s, mid);
    //cout<<p<<" "<<re<<endl;
    if (mid < r) re =min(re, getsum(l, r, r(p), mid + 1, t));
    //cout<<p<<" "<<re<<" "<<mid<<" "<<s<<" "<<t<<endl;
    return re;
}

void update(ll l, ll r, ll c, ll s = 1, ll t = 1e9+2, ll p = 1) {
    // [l,r] 为查找区间,[s,t] 为当前区间
    if (s >= l && t <= r) {
        sum(p) = c ;
        add(p) = c;
        return;
    }
    pushdown(p, t - s + 1);
    ll mid = (s + t ) / 2;
    if (mid >= l) update(l, r, c, s, mid, l(p));
    if (mid < r) update(l, r, c, mid + 1, t, r(p));
    sum(p) = min(sum(l(p)) , sum(r(p)));
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,m;
    cin>>n>>m;
    while(m--){
        int a,l,r;
        cin>>a>>l>>r;
        if(a==1) update(l,r,1);
        else {
            if(getsum(l,r)==0){
                cout<<"NO"<<endl;
            }
            else{
                cout<<"YES"<<endl;
            }
        }
    }
    return 0;
}

线段树离散化：

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <iomanip>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <string>
#include <cstring>
#include <vector>
#include <cmath>
#include <bitset>
#include <ext/rope>
#include <unordered_set>
#include <unordered_map>
#define int long long
#define inf 0x3f3f3f3f
#define ios ios::sync_with_stdio(false)
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 3e5 + 10, M = 510;
const double eps = 1e-5;

struct node {int sum = 0, lazy = 0;};

node tree[N << 2];
int a[N];

void pushup(int root)
{
    tree[root].sum = tree[root << 1].sum + tree[root << 1 | 1].sum;
}

void pushdown(int root, int left, int right)
{
    int mid = left + right >> 1;
    if (tree[root].lazy)
    {
        tree[root << 1].lazy = tree[root].lazy;
        tree[root << 1].sum = mid - left + 1;
        tree[root << 1 | 1].lazy = tree[root].lazy;
        tree[root << 1 | 1].sum = right - mid;
        tree[root].lazy = 0;
    }
}

// [L, R] all add num
void updata(int l, int r, int L, int R, int root)
{
    if (l >= L && r <= R)
    {
        tree[root].lazy = 1;
        tree[root].sum = r - l + 1;
        return;
    }
    if (l == r) return;
    pushdown(root, l, r);
    int m = l + r >> 1;
    if(L <= m) updata(l, m, L, R, root << 1);
    if(R > m) updata(m + 1, r, L, R, root << 1 | 1);
    pushup(root);
}

// query the sum of [L, R]
int query(int l, int r, int L, int R, int root)
{
    if (l >= L && r <= R) return tree[root].sum;
    pushdown(root, l, r);
    int m = l + r >> 1;
    int res = 0;
    if(L <= m) res += query(l, m, L, R, root << 1);
    if(R > m) res += query(m + 1, r, L, R, root << 1 | 1);
    pushup(root);
    return res;
}

vector<int> alls;
int find(int x) {return lower_bound(alls.begin(), alls.end(), x) - alls.begin() + 1;}
struct Q {int opt, l, r;}qy[N];

void solve()
{
    int m, n; cin>>m>>n;
    for(int i = 1;i <= n;i ++) cin>>qy[i].opt>>qy[i].l>>qy[i].r;
    for(int i = 1;i <= n;i ++) alls.push_back(qy[i].l), alls.push_back(qy[i].r);
    sort(alls.begin(), alls.end());
    alls.erase(unique(alls.begin(), alls.end()), alls.end());

    m = alls.size() - 1;
    for(int i = 1;i <= n;i ++)
    {
        int l = find(qy[i].l), r = find(qy[i].r) - 1;
        if(qy[i].opt == 1) updata(1, m, l, r, 1);
        else cout<<(query(1, m, l, r, 1) == r - l + 1 ? "YES" : "NO")<<endl;
    }
}
signed main()
{
    ios;
    int t = 1; //cin>>t;
    while(t --) solve();
    return 0;
}

RF.海阔天空

由于数据范围较小，根据题意模拟即可。

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <iomanip>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <string>
#include <cstring>
#include <vector>
#include <cmath>
#include <bitset>
#include <ext/rope>
#include <unordered_set>
#include <unordered_map>
#define int long long
using namespace std;
typedef long long ll;

const int N = 1e3 + 10, M = 510;
const double eps = 1e-5;

int a[N];

int gcd(int x, int y)
{
    if(x % y == 0) return y;
    return gcd(y, x % y);
}

void solve()
{
    int n; cin>>n;
    for(int i = 1;i <= n;i ++) cin>>a[i];
    for(int i = 1;i <= n;i ++)
    {
        int cnt = 0;
        if(a[i] == 1) cnt ++;
        for(int j = 1;j < a[i];j ++)
            if(gcd(a[i], j) == 1) cnt ++;
        cout<<cnt<<" ";
    }
    cout<<endl;
}

signed main()
{
    ios;
    int t = 1; //cin>>t;
    while(t --) solve();
    return 0;
}