2018 icpc 沈阳

左手的ㄟ右手 2023-06-03 02:53 23阅读 0赞

[https://codeforces.com/gym/101955][https_codeforces.com_gym_101955]

## J ##

签到

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

## C ##

先乘一个k!，并假定前k个数是有序的

最长上升序列长度是n-1，就要把一个数字排除在外，就要把一个数字插入到其他位置

分成三种情况：前k个数里的某个数插入到后n-k个里，后n-k个数插入到前k个数里，后n-k个数插入到后n-k个数里。

分别统计，要注意相邻两个数交换的情况，只能被统计一次。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

## G ##

圆上的整数点数量是相当有限的，对于这个题来说，询问的半径是固定不变的，可以预处理圆上的整点，由于点的数量很小，接下来就暴力修改查询即可。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<iostream>
    #include<cstring>
    #include<cstdio>
    #include<algorithm>
    #include<string>
    #include <set>
    #include <map>
    #include <queue>
    #include <cmath>
    #define ll long long
    #define fo(i,l,r) for(int i = l;i <= r;i++)
    #define fd(i,l,r) for(int i = r;i >= l;i--)
    using namespace std;
    const int maxn = 6050,maxk=1e7+5;
    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;
    }
    const int fx[4] = {-1,1,-1,1};
    const int fy[4] = {-1,-1,1,1};
    vector<int> st[maxk],st2[maxk];
    int n,m,flag;
    ll weight[maxn+10][maxn+10];
    int flags[maxn+10][maxn+10];
    bool judge(int y,int x){
        return y>=0&&y<=maxn&&x>=0&&x<=maxn;
    }
    void add(int y,int x,ll w){
        weight[y][x] = w;
        flags[y][x] = flag;
    }
    void del(int y,int x){
        weight[y][x] = 0;
        flags[y][x]--;
    }
    void inc(int y,int x,ll k,ll w){
        int sz = st[k].size();
        int dy,dx,nowy,nowx;
        fo(i,0,sz-1){
            dx = st[k][i];
            dy = st2[k][i];
            fo(j,0,3){
                if(dx==0&&(j==1||j==3))continue;
                if(dy==0&&(j==2||j==3))continue;
                nowy = y + dy*fy[j];
                nowx = x + dx*fx[j];
                if(!judge(nowy,nowx))continue;
                if(flags[nowy][nowx]==flag) weight[nowy][nowx] += w;
            }
    
        }
    }
    ll query(int y,int x,ll k){
        int sz = st[k].size();
        int dy,dx,nowy,nowx;
        ll ans = 0;
        fo(i,0,sz-1){
            dx = st[k][i];
            dy = st2[k][i];
            fo(j,0,3){
                if(dx==0&&(j==1||j==3))continue;
                if(dy==0&&(j==2||j==3))continue;
                nowy = y + dy*fy[j];
                nowx = x + dx*fx[j];
                if(judge(nowy,nowx)){
                    if(flags[nowy][nowx]==flag)ans += weight[nowy][nowx];
                }
            }
        }
        return ans;
    }
    int main(){
        ios::sync_with_stdio(false);
        int T,Case=0;
        T=read();
        ll lastans = 0;
        fo(i, 0, 6000) {
            fo(j, 0, 6000) {
                if (i * i + j * j > 1e7) break;
                st[i * i + j * j].push_back(i);
                st2[i * i + j * j].push_back(j);
            }
        }
        while(T--) {
            flag++;
            lastans=0;
            int y, x, cmd;
            ll k, w;
            cout<<"Case #"<<++Case<<":"<<endl;
            n = read();
            m = read();
            fo(i, 1, n) {
                y = read();
                x = read();
                w = read();
                add(y, x, w);
            }
            fo(i, 1, m) {
                cmd = read();
                y = read();
                x = read();
                y = (y + lastans) % 6000ll + 1ll;
                x = (x + lastans) % 6000ll + 1ll;
                if (cmd == 1) {
                    w = read();
                    add(y, x, w);
                } else if (cmd == 2) {
                    del(y, x);
                } else if (cmd == 3) {
                    k = read();
                    w = read();
                    inc(y, x, k, w);
                } else {
                    k = read();
                    cout << (lastans = query(y, x, k)) << endl;
                }
            }
        }
        return 0;
    }

## K ##

首先考虑一般意义上的约瑟夫环问题，把k-1个人删去后，将k...n,0..k-2重新编号，就变成一个规模为n-1的一模一样的问题了。

考虑这个题，这次求的不是最后一个，而是第m个人把k-1删去之后，就变成了从n-1个人里找第m-1个人了。

直接递推需要一个o(m)的循环，但是题目范围说m和k总有一个很小，当k很小m很大时，我们可以让它直接顶到头而不是一项一项递推，加速递推过程。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

## L ##

计算几何。

首先将外部圆与中心圆的交点求出，先看能不能取到直径，可以取到的充要条件是，存在一个交点，它的对称点没有被外部圆切去。

若不能取到直径，所有交点两两连线，去距离的最大值。

本地精度存在一些问题，long double会导致WA，只有double可以过，具体原因待探究。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <iostream>
    #include <cstdio>
    #include <string>
    #include <cstring>
    #include <algorithm>
    #include <cmath>
    #include <stack>
    #include <vector>
    #include <set>
    #include <cmath>
    #include <queue>
    #include <map>
    #define ll long long
    #define ld double
    #define lson rt << 1, l, m
    #define pi acos(-1)
    #define rson rt << 1 | 1, m + 1, r
    #define fo(i, l, r) for (long long i = l; i <= r; i++)
    #define fd(i, l, r) for (long long i = r; i >= l; i--)
    #define mem(x) memset(x, 0, sizeof(x))
    #define eps 1e-10
    using namespace std;
    const ll maxn = 1050;
    const ll mod = 998244353;
    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;
    }
    struct dat
    {
        ld v;
        bool isr;
        int p;
        friend bool operator<(dat a, dat b)
        {
            return a.v < b.v;
        }
    };
    int cnt;
    ll n;
    ld R;
    ld px[maxn], py[maxn], pr[maxn], ans;
    ld fpx[maxn], fpy[maxn];
    dat ang[maxn * 2];
    dat fang[maxn * 2];
    ld getang(ld a, ld b, ld c)
    {
        return acos((a * a + b * b - c * c) / (a * b + a * b));
    }
    ld tryang(ld agl)
    {
        if (agl < 0)
            agl = -agl;
        return R * sin(agl / 2.0) * 2.0;
    }
    int main()
    {
        int T;
        T = read();
        int tt = 0;
        while (T--)
        {
            tt++;
            cnt = 0;
            n = read();
            R = read();
            ld dis, baseAngle;
            fo(i, 1, n)
            {
                px[i] = read();
                py[i] = read();
                pr[i] = read();
                dis = sqrt(px[i] * px[i] + py[i] * py[i]);
                baseAngle = atan2(py[i], px[i]);
                if (pr[i] + R < dis)
                {
                    continue;
                }
                if (fabs(R - pr[i]) > dis)
                {
                    continue;
                }
    
                ang[cnt + 1].v = baseAngle - getang(dis, R, pr[i]);
                ang[cnt + 2].v = baseAngle + getang(dis, R, pr[i]);
                if (ang[cnt + 1].v < 0)
                    ang[cnt + 1].v += pi + pi;
                if (ang[cnt + 1].v >= pi + pi)
                    ang[cnt + 1].v -= pi + pi;
                if (ang[cnt + 2].v < 0)
                    ang[cnt + 2].v += pi + pi;
                if (ang[cnt + 2].v >= pi + pi)
                    ang[cnt + 2].v -= pi + pi;
                cnt += 2;
            }
            if (cnt == 0)
                ans = R + R;
            fo(i, 1, cnt)
            {
                fpx[i] = -R * cos(ang[i].v);
                fpy[i] = -R * sin(ang[i].v);
            }
            ans = 0.0;
            fo(i, 1, cnt)
            {
                fo(j, i + 1, cnt)
                {
                    ans = max(ans, tryang(ang[i].v - ang[j].v));
                }
            }
            ld tx, ty;
            fo(i, 1, cnt)
            {
                bool ok = false;
                fo(j, 1, n)
                {
                    if ((fpx[i] - px[j]) * (fpx[i] - px[j]) + (fpy[i] - py[j]) * (fpy[i] - py[j]) < pr[j] * pr[j])
                    {
                        ok = true;
                        break;
                    }
                }
                if (!ok)
                {
                    ans = R + R;
                    break;
                }
            }
            printf("Case #%d: %.15lf\n", tt, ans);
        }
        return 0;
    }

转载于:https://www.cnblogs.com/hyfer/p/11524344.html

[https_codeforces.com_gym_101955]: https://codeforces.com/gym/101955
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230601/9782b7dfcfc8472dbfc42683b9bad7b5.png