分类笔记下的文章

Solution Set -「ARC 109」

29-01-2021
笔记
0 comment

「ARC 109A」Hands

讨论即可，除了煞笔出题人写了个死马的题面。

#include<cstdio>
#include<algorithm>
using namespace std;
int a,b,x,y,ans;
int main()
{
    scanf("%d%d%d%d",&a,&b,&x,&y);
    if(a>b)    printf("%d\n",min(x<<1,y)*max(0,abs(a-b)-1)+x);
    else    printf("%d\n",min(x<<1,y)*max(0,abs(a-b))+x);
    return 0;
}

「ARC 109B」log

Link.

要贪心的取的话，肯定是先把 $n+1$ 取了，然后我们来二分。

$1-n$ 分别有 $n+1$ 到 $2$ 种方法可以组成他。

然后来考虑怎么 check。

可以知晓，如果没有这一块多的木块，就一定需要 $n$ 块木头。

然后就按开头那个贪心，把 $n+1$ 从 $1$ 分完，剩下的再依次分。

#include<cstdio>
unsigned long long n;
bool check(unsigned long long x)
{
    return (x*(x+1)>>1)<=n+1;
}
unsigned long long search(unsigned long long l,unsigned long long r)
{
    unsigned long long res=0;
    while(l<=r)
    {
        unsigned long long mid=(l+r)>>1;
        if(check(mid))
        {
            l=mid+1;
            res=n-mid+1;
        }
        else    r=mid-1;
    }
    return res;
}
int main()
{
    scanf("%llu",&n);
    printf("%llu\n",search(1,2e9));
    return 0;
}

「ARC 109C」Large RPS Tournament

Link.

$2^{k}$！好耶！！！

考虑倍增 DP。设 $f_{i,j}$ 为区间 $[i,i+2^{j}-1]$ 的 winner's hand。

设计一个函数 $\text{tournament}(P,Q)$ 为 $P$、$Q$ 比武后的赢家。

转移即

$$ f_{i,j}=\text{tournament}(f_{i,j-1},f_{i+2^{j-1},j-1}) $$

当然你不能直接用 $2^{k}$ 当成序列来做，反正他是循环节我们直接做 $k$ 轮最后合并即可。

实际实现时不需要这么写（主要是写不来）（好像可以记忆化？）。

#include<string>
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
string s;
int n,k;
char tour(char one,char ano)
{
    if(one=='R')
    {
        if(ano=='R')    return 'R';
        else if(ano=='P')    return 'P';
        else    return 'R';
    }
    else if(one=='P')
    {
        if(ano=='R')    return 'P';
        else if(ano=='P')    return 'P';
        else    return 'S';
    }
    else
    {
        if(ano=='R')    return 'R';
        else if(ano=='P')    return 'S';
        else    return 'S';
    }
}
int main()
{
    scanf("%d%d",&n,&k);
    cin>>s;
    while(k--)
    {
        string tmp=s+s;
        for(int i=0;i<n;++i)    s[i]=tour(tmp[i<<1],tmp[i<<1|1]);
    }
    printf("%c\n",s[0]);
    return 0;
}

「ARC 109D」L

图画出来差不多，向目标进发，步数下界就出来了 $\max\{|x|,|y|\}$。

这张图是在这里嫖的：

注意特判一些奇怪的情况，具体自己看代码吧吧吧吧。

#include<cstdio>
#include<algorithm>
using namespace std;
int t,onex,oney,anox,anoy,exx,exy,finalx,finaly;
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%d%d%d%d",&onex,&oney,&anox,&anoy,&exx,&exy);
        finalx=min(onex,min(anox,exx));
        finaly=min(oney,min(anoy,exy));
        finalx=(finalx<<1)+(finalx!=onex)+(finalx!=anox)+(finalx!=exx)-1;
        finaly=(finaly<<1)+(finaly!=oney)+(finaly!=anoy)+(finaly!=exy)-1;
        printf("%d\n",max(abs(finalx),abs(finaly))+((finalx==finaly)&&(finalx>1||finalx<0)));
    }
    return 0;
}

「ARC 109E」1D Reversi Builder

Link.

「ARC 109F」1D Kingdom Builder

Link.

Solution -「THUPC 2019」Duckchess

21-01-2021
笔记
0 comment

Description

Link.

大模拟是不可能给你概括题意的。

Solution

（据说鸭棋题解用这个标题很吉利）（这里是被点名批评的长度 19k 的打法）（先说好代码里 Chinglish 满地，尽量不要吐槽吧……）

首先我们不需要仔细阅读每一种棋的判定方法及其走法，写的时候照抄即可。

理一下大体逻辑。首先开一个全局的棋盘 vector<vector<string> > evemap;，一个 over 表示棋局是否结束。

然后是棋手的结构体：

struct chess
{
    string color;
    string getcolor(int x,int y);
    string getchess(int x,int y);
    bool outside(int x,int y);
    bool exist(int x,int y);
    bool thereok(int x,int y);
    bool occaptain(int sx,int sy,int tx,int ty);
    bool ocguard(int sx,int sy,int tx,int ty);
    bool ocelephant(int sx,int sy,int tx,int ty);
    bool ochorse(int sx,int sy,int tx,int ty);
    bool occar(int sx,int sy,int tx,int ty);
    bool ocduck(int sx,int sy,int tx,int ty);
    bool ocsoldier(int sx,int sy,int tx,int ty);
    string checkgoi();
    bool checkove();
    void moving(int sx,int sy,int tx,int ty);
    string final(string s);
    vector<string> movecaptain(int sx,int sy,int tx,int ty);
    vector<string> moveguard(int sx,int sy,int tx,int ty);
    vector<string> moveelephant(int sx,int sy,int tx,int ty);
    vector<string> movehorse(int sx,int sy,int tx,int ty);
    vector<string> movecar(int sx,int sy,int tx,int ty);
    vector<string> moveduck(int sx,int sy,int tx,int ty);
    vector<string> movesoldier(int sx,int sy,int tx,int ty);
    vector<string> execute(int sx,int sy,int tx,int ty); 
}redplay,blueplay;

string color 表示棋手的颜色。

这里先来解释一下各个函数的含义：

oc-chess 和 move-chess 形式：
- bool oc-chess(sx,sy,tx,ty)：这个表示 chess 棋从 $(s_{x},s_{y})$ 走到 $(t_{x},t_{y})$ 是否合法。
- vector<string> move-chess(sx,sy,tx,ty)：这个标识 chess 棋从 $(s_{x},s_{y})$ 走到 $(t_{x},t_{y})$ 最终返回的东西。
其他的一些杂函数：
- string getcolor(x,y)：棋盘位置 $(x,y)$ 的棋的颜色，如果没有则返回 empty。
- string getchess(x,y)：棋盘位置 $(x,y)$ 的棋的棋子类型，如果没有则返回 empty。
- bool outside(int x,int y)：$(x,y)$ 是否出界。
- bool exist(int x,int y)：$(x,y)$ 是否存在任意一方的棋子。
- bool thereok(int x,int y)：$(x,y)$ 是否不存在同色棋子且没有出界。
- string checkgoi()：检查是否有将军。（通过遍历棋盘实现）
- bool checkove()：是否有任意一方的将军被吃。
- void moving(int sx,int sy,int tx,int ty)：把 $(s_{x},s_{y})$ 的棋子移到 $(t_{x},t_{y})$。
- string final(string s)：我棋盘存储棋子的形式是 color-chess，这个函数的作用就是转为题目的形式 color chess。
- void execute(sx,sy,tx,ty)：处理一次询问。

结构差不多就这里，接下来说一下具体实现。

首先用个 void mapinitial() 初始化棋盘。
然后都询问，处理询问，调用 execute()。
输出。

好的我承认这个实现方法特别烂。

/*
function(vector<string>)(with prefix 'move') result:
    "invcom": invalid command
    "color-chess": the chess(opposite) which is eaten
    "beaten": have the Jiangjun been complete
    "over": have the game been over
vector[0][1][2][3]
*/
#include<queue>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
const int h=10,w=9;
int over;
//string evemap[20][20];
vector<vector<string> > evemap;
void printmap()
{
    for(int i=0;i<h;++i)
    {
        for(int j=0;j<w;++j)    printf("%14s",evemap[i][j].c_str()),printf("[%d %d]",i,j);
        printf("\n");
    }
}
struct chess
{
    string color;
    string getcolor(int x,int y)
    /*
        result:
            "empty": empty place
            "red": red chess
            "blue": blue chess
    */
    {
        string res,s=evemap[x][y];
        if(s=="empty")    return "empty";
        else
        {
            for(int i=0;i<s.length();++i)
            {
                if(s[i]=='-')    break;
                res+=s[i];
            }
            return res;
        }
    }
    string getchess(int x,int y)
    /*
        result:
            each string has the same meaning as 'evemap'
    */
    {
        string res,s=evemap[x][y];
        if(s=="empty")    return "empty";
        else
        {
            int st=0;
            for(int i=0;i<s.length();++i)
            {
                if(st)    res+=s[i];
                else if(s[i]=='-')    st=1;
            }
            return res;
        }
    }
    bool outside(int x,int y)
    {
        if(x<0||x>=h||y<0||y>=w)    return 1;
        else    return 0;
    }
    bool exist(int x,int y)
    {
        if(getchess(x,y)=="empty")    return 0;
        else    return 1;
    }
    bool thereok(int x,int y)
    /*
        result:
            1: this place is walkable
            0: this place is occupied or (x,y) is out of range
        means:
            1. isn't out of range
            2. (x,y) has no same color chess or is empty
    */
    {
        if(outside(x,y))    return 0;
        else if(evemap[x][y]!="empty"&&getcolor(x,y)==color)    return 0;
        else    return 1;
    }
    bool occaptain(int sx,int sy,int tx,int ty)
    {
        if(!thereok(tx,ty))    return 0;
        for(int i=-1;i<=1;++i)
        {
            if(i)
            {
                if(thereok(sx+i,sy)&&tx==(sx+i)&&ty==sy)    return 1;
                else if(thereok(sx,sy+i)&&tx==sx&&ty==(sy+i))    return 1;
            }
        }
        return 0;
    }
    bool ocguard(int sx,int sy,int tx,int ty)
    {
        if(!thereok(tx,ty))    return 0;
        for(int i=-1;i<=1;++i)
        {
            if(i)
            {
                if(thereok(sx+i,sy+i)&&tx==(sx+i)&&ty==(sy+i))    return 1;
                if(thereok(sx+i,sy-i)&&tx==(sx+i)&&ty==(sy-i))    return 1;
            }
        }
        return 0;
    }
    bool ocelephant(int sx,int sy,int tx,int ty)
    {
        if(!thereok(tx,ty))    return 0;
        for(int i=-1;i<=1;++i)
        {
            if(i)
            {
                for(int j=-1;j<=1;++j)
                {
                    if(j)
                    {
                        if(thereok(sx+i,sy+j))
                        {
                            if(thereok(sx+(i<<1),sy+(j<<1))&&tx==(sx+(i<<1))&&ty==(sy+(j<<1)))    return 1;
                        }
                    }
                }
            }
        }
        return 0;
    }
    bool ochorse(int sx,int sy,int tx,int ty)
    {
        if(!thereok(tx,ty))    return 0;
        for(int i=-1;i<=1;++i)
        {
            if(i)
            {
                for(int j=-1;j<=1;++j)
                {
                    if(j)
                    {
//                        printf("[{%d %d} {%d %d} {%d %d %d}]\n",sx,sy+j,sx+i,sy+(j<<1),outside(sx,sy+j),exist(sx,sy+j),!outside(sx,sy+j)&&!exist(sx,sy+j));
                        if(!outside(sx+i,sy)&&!exist(sx+i,sy))
                        {
                            if(thereok(sx+(i<<1),sy+j)&&tx==(sx+(i<<1))&&ty==(sy+j))    return 1;
                        }
                        if(!outside(sx,sy+j)&&!exist(sx,sy+j))
                        {
                            if(thereok(sx+i,sy+(j<<1))&&tx==(sx+i)&&ty==(sy+(j<<1)))    return 1;
                        }
                    }
                }
            }
        }
        return 0;
    }
    bool occar(int sx,int sy,int tx,int ty)
    {
        if(!thereok(tx,ty))    return 0;
        if(sx==tx)
        {
            int delta;
            if(sy<ty)    delta=1;
            else    delta=-1;
            for(int j=sy;j^ty;j+=delta)
            {
                if((j^sy)&&exist(sx,j))    return 0;
            }
            return 1;
        }
        else if(sy==ty)
        {
            int delta;
            if(sx<tx)    delta=1;
            else    delta=-1;
            for(int i=sx;i^tx;i+=delta)
            {
//                printf("[{%d %d}]\n",i,sy);
                if((i^sx)&&exist(i,sy))    return 0;
            }
            return 1;
        }
        else    return 0;
    }
    bool ocduck(int sx,int sy,int tx,int ty)
    {
        if(!thereok(tx,ty))    return 0;
        for(int i=-1;i<=1;++i)
        {
            if(i)
            {
                for(int j=-1;j<=1;++j)
                {
                    if(j)
                    {
                        if(!outside(sx+(i<<1),sy+j)&&!exist(sx+(i<<1),sy+j)&&!outside(sx+i,sy)&&!exist(sx+i,sy))
                        {
//                            printf("[{%d %d} {%d %d} {%d %d} {%d %d} {%d %d} {%d %d}]\n",sx,sy,tx,ty,sx+i,sy,sx+(i<<1),sy+j,sx+((i<<1)+i),sy+(j<<1),thereok(sx+((i<<1)+i),sy+(j<<1)),tx==(sx+((i<<1)+i)&&ty==(sy+(j<<1))));
                            if(thereok(sx+((i<<1)+i),sy+(j<<1))&&tx==(sx+((i<<1)+i))&&ty==(sy+(j<<1)))    return 1;
                        }
                        if(!outside(sx+i,sy+(j<<1))&&!exist(sx+i,sy+(j<<1))&&!outside(sx,sy+j)&&!exist(sx,sy+j))
                        {
                            if(thereok(sx+(i<<1),sy+((j<<1)+j))&&tx==(sx+(i<<1))&&ty==(sy+((j<<1)+j)))    return 1;
                        }
                    }
                }
            }
        }
        return 0;
    }
    bool ocsoldier(int sx,int sy,int tx,int ty)
    {
        if(!thereok(tx,ty))    return 0;
        for(int i=-1;i<=1;++i)
        {
            if(i)
            {
                if(thereok(sx+i,sy)&&tx==(sx+i)&&ty==sy)    return 1;
                if(thereok(sx,sy+i)&&tx==sx&&ty==(sy+i))    return 1;
                if(thereok(sx+i,sy+i)&&tx==(sx+i)&&ty==(sy+i))    return 1;
                if(thereok(sx+i,sy-i)&&tx==(sx+i)&&ty==(sy-i))    return 1;
            }
        }
        return 0;
    }
    string checkgoi()
    /*
        result:
            "not": Jiangjun didn't happened
            "red": the RED general has been Jiangjuned
            "blue": the BLUE general has been Jiangjuned
    */
    {
        if(over)    return "not";
        for(int i=0;i<h;++i)
        {
            for(int j=0;j<w;++j)
            {
                string curcol=getcolor(i,j),curche=getchess(i,j),revcol;
                if(curcol=="red")    revcol="blue";
                else if(curcol=="blue")    revcol="red";
                else    revcol="empty";
                if(curche!="empty")
                {
                    if(curche=="captain")
                    {
                        for(int k=-1;k<=1;++k)
                        {
                            if(k)
                            {
                                if(!outside(i+k,j))
                                {
                                    string nxtcol=getcolor(i+k,j),nxtche=getchess(i+k,j);
                                    if(nxtcol==revcol&&nxtche=="captain")    return nxtcol;
                                }
                                if(!outside(i,j+k))
                                {
                                    string nxtcol=getcolor(i,j+k),nxtche=getchess(i,j+k);
                                    if(nxtcol==revcol&&nxtche=="captain")    return nxtcol;
                                }
                            }
                        }
                    }
                    else if(curche=="guard")
                    {
                        for(int k=-1;k<=1;++k)
                        {
                            if(k)
                            {
                                if(!outside(i+k,j+k))
                                {
                                    string nxtcol=getcolor(i+k,j+k),nxtche=getchess(i+k,j+k);
                                    if(nxtcol==revcol&&nxtche=="captain")    return nxtcol;
                                }
                                if(!outside(i+k,j-k))
                                {
                                    string nxtcol=getcolor(i+k,j-k),nxtche=getchess(i+k,j-k);
                                    if(nxtcol==revcol&&nxtche=="captain")    return nxtcol;
                                }
                            }
                        }
                    }
                    else if(curche=="elephant")
                    {
                        for(int k=-1;k<=1;++k)
                        {
                            if(k)
                            {
                                for(int l=-1;l<=1;++l)
                                {
                                    if(l)
                                    {
                                        if(!outside(i+(k<<1),j+(l<<1))&&!exist(i+k,j+l))
                                        {
                                            string nxtcol=getcolor(i+(k<<1),j+(l<<1)),nxtche=getchess(i+(k<<1),j+(l<<1));
                                            if(nxtcol==revcol&&nxtche=="captain")    return nxtcol; 
                                        }
                                    }
                                }
                            }
                        }
                    }
                    else if(curche=="horse")
                    {
                        for(int k=-1;k<=1;++k)
                        {
                            if(k)
                            {
                                for(int l=-1;l<=1;++l)
                                {
                                    if(l)
                                    {
                                        if(!outside(i+(k<<1),j+l)&&!exist(i+k,j))
                                        {
                                            string nxtcol=getcolor(i+(k<<1),j+l),nxtche=getchess(i+(k<<1),j+l);
                                            if(nxtcol==revcol&&nxtche=="captain")    return nxtcol;
                                        }
                                        if(!outside(i+k,j+(l<<1))&&!exist(i,j+l))
                                        {
                                            string nxtcol=getcolor(i+k,j+(l<<1)),nxtche=getchess(i+k,j+(l<<1));
                                            if(nxtcol==revcol&&nxtche=="captain")    return nxtcol;
                                        }
                                    }
                                }
                            }
                        }
                    }
                    else if(curche=="car")
                    {
                        for(int k=i;k<h;++k)
                        {
                            if(!outside(k,j))
                            {
                                string nxtcol=getcolor(k,j),nxtche=getchess(k,j);
                                if(nxtche!="empty")
                                {
                                    if(nxtche=="captain")    return nxtcol;
                                    break;
                                }
                            }
                        }
                        for(int l=j;l<w;++l)
                        {
                            if(!outside(i,l))
                            {
                                string nxtcol=getcolor(i,l),nxtche=getchess(i,l);
                                if(nxtche!="empty")
                                {
                                    if(nxtche=="captain")    return nxtcol;
                                    break;
                                }
                            }
                        }
                    }
                    else if(curche=="duck")
                    {
                        for(int k=-1;k<=1;++k)
                        {
                            if(k)
                            {
                                for(int l=-1;l<=1;++l)
                                {
                                    if(l)
                                    {
                                        if(!outside(i+((k<<1)+k),j+(l<<1))&&!exist(i+(k<<1),j+l)&&!exist(i+k,j))
                                        {
                                            string nxtcol=getcolor(i+((k<<1)+k),j+(l<<1)),nxtche=getchess(i+((k<<1)+k),j+(l<<1));
                                            if(nxtcol==revcol&&nxtche=="captain")    return nxtcol;
                                        }
                                        if(!outside(i+(k<<1),j+((l<<1)+l))&&!exist(i+k,j+(l<<1))&&!exist(i,j+l))
                                        {
                                            string nxtcol=getcolor(i+(k<<1),j+((l<<1)+l)),nxtche=getchess(i+(k<<1),j+((l<<1)+l));
                                            if(nxtcol==revcol&&nxtche=="captain")    return nxtcol;
                                        }
                                    }
                                }
                            }
                        }
                    }
                    else if(curche=="soldier")
                    {
                        for(int k=-1;k<=1;++k)
                        {
                            if(k)
                            {
                                if(!outside(i+k,j))
                                {
                                    string nxtcol=getcolor(i+k,j),nxtche=getchess(i+k,j);
                                    if(nxtcol==revcol&&nxtche=="captain")    return nxtcol;
                                }
                                if(!outside(i,j+k))
                                {
                                    string nxtcol=getcolor(i,j+k),nxtche=getchess(i,j+k);
                                    if(nxtcol==revcol&&nxtche=="captain")    return nxtcol;
                                }
                                if(!outside(i+k,j+k))
                                {
                                    string nxtcol=getcolor(i+k,j+k),nxtche=getchess(i+k,j+k);
                                    if(nxtcol==revcol&&nxtche=="captain")    return nxtcol;
                                }
                                if(!outside(i+k,j-k))
                                {
                                    string nxtcol=getcolor(i+k,j-k),nxtche=getchess(i+k,j-k);
                                    if(nxtcol==revcol&&nxtche=="captain")    return nxtcol;
                                }
                            }
                        }
                    }
                }
            }
        }
        return "not";
    }
    bool checkove()
    /*
        result:
            0: the game isn't over
            1: the game is still alive
    */
    {
        bool red=0,blue=0;
        for(int i=0;i<h;++i)
        {
            for(int j=0;j<w;++j)
            {
                if(getchess(i,j)=="captain")
                {
//                    printf("[%d %d]\n",i,j);
                    if(getcolor(i,j)=="red")    red=1;
                    else    blue=1;
                }
            }
        }
        return !red||!blue;
    }
    void moving(int sx,int sy,int tx,int ty)
    {
        evemap[tx][ty]=evemap[sx][sy];
        evemap[sx][sy]="empty";
    }
    string final(string s)
    {
        if(s=="empty")    return "empty";
        else
        {
            for(int i=0;i<s.length();++i)
            {
                if(s[i]=='-')
                {
                    s[i]=' ';
                    break;
                }
            }
            return s;
        }
    }
    vector<string> movecaptain(int sx,int sy,int tx,int ty)
    {
        vector<string> res;
//        printf("%s %s\n",getcolor(sx,sy).c_str(),color.c_str());
        if(over||!occaptain(sx,sy,tx,ty)||getcolor(sx,sy)!=color)
        {
            res.push_back("Invalid command");
            return res;
        }
        else
        {
            string cur,eat,goi,ove,col,lor;
            col=getcolor(sx,sy);
            lor=getcolor(tx,ty);
            cur=getchess(sx,sy);
            eat=getchess(tx,ty);
            if(lor=="empty")    lor="";
            if(eat=="empty")    eat="NA";
            moving(sx,sy,tx,ty);
            if(checkgoi()!="not")    goi="yes";
            else    goi="no";
            if(checkove())
            {
                over=1;
                ove="yes";
            }
            else    ove="no";
            cur=final(cur);
            res.push_back(col+" "+cur);
            if(lor!="") res.push_back(lor+" "+eat);
            else    res.push_back(eat);
            res.push_back(goi);
            res.push_back(ove);
            return res;
        }
    }
    vector<string> moveguard(int sx,int sy,int tx,int ty)
    {
        vector<string> res;
        if(over||!ocguard(sx,sy,tx,ty)||getcolor(sx,sy)!=color)
        {
            res.push_back("Invalid command");
            return res;
        }
        else
        {
            string cur,eat,goi,ove,col,lor;
            col=getcolor(sx,sy);
            lor=getcolor(tx,ty);
            cur=getchess(sx,sy);
            eat=getchess(tx,ty);
            if(lor=="empty")    lor="";
            if(eat=="empty")    eat="NA";
            moving(sx,sy,tx,ty);
            if(checkgoi()!="not")    goi="yes";
            else    goi="no";
            if(checkove())
            {
                over=1;
                ove="yes";
            }
            else    ove="no";
            cur=final(cur);
            res.push_back(col+" "+cur);
            if(lor!="") res.push_back(lor+" "+eat);
            else    res.push_back(eat);
            res.push_back(goi);
            res.push_back(ove);
            return res;
        }
    }
    vector<string> moveelephant(int sx,int sy,int tx,int ty)
    {
        vector<string> res;
        if(over||!ocelephant(sx,sy,tx,ty)||getcolor(sx,sy)!=color)
        {
            res.push_back("Invalid command");
            return res;
        }
        else
        {
            string cur,eat,goi,ove,col,lor;
            col=getcolor(sx,sy);
            lor=getcolor(tx,ty);
            cur=getchess(sx,sy);
            eat=getchess(tx,ty);
            if(lor=="empty")    lor="";
            if(eat=="empty")    eat="NA";
            moving(sx,sy,tx,ty);
            if(checkgoi()!="not")    goi="yes";
            else    goi="no";
            if(checkove())
            {
                over=1;
                ove="yes";
            }
            else    ove="no";
            cur=final(cur);
            res.push_back(col+" "+cur);
            if(lor!="") res.push_back(lor+" "+eat);
            else    res.push_back(eat);
            res.push_back(goi);
            res.push_back(ove);
            return res;
        }
    }
    vector<string> movehorse(int sx,int sy,int tx,int ty)
    {
        vector<string> res;
        if(over||!ochorse(sx,sy,tx,ty)||getcolor(sx,sy)!=color)
        {
            res.push_back("Invalid command");
            return res;
        }
        else
        {
            string cur,eat,goi,ove,col,lor;
            col=getcolor(sx,sy);
            lor=getcolor(tx,ty);
            cur=getchess(sx,sy);
            eat=getchess(tx,ty);
            if(lor=="empty")    lor="";
            if(eat=="empty")    eat="NA";
            moving(sx,sy,tx,ty);
            if(checkgoi()!="not")    goi="yes";
            else    goi="no";
            if(checkove())
            {
                over=1;
                ove="yes";
            }
            else    ove="no";
            cur=final(cur);
            res.push_back(col+" "+cur);
            if(lor!="") res.push_back(lor+" "+eat);
            else    res.push_back(eat);
            res.push_back(goi);
            res.push_back(ove);
            return res;
        }
    }
    vector<string> movecar(int sx,int sy,int tx,int ty)
    {
        vector<string> res;
        if(over||!occar(sx,sy,tx,ty)||getcolor(sx,sy)!=color)
        {
            res.push_back("Invalid command");
            return res;
        }
        else
        {
            string cur,eat,goi,ove,col,lor;
            col=getcolor(sx,sy);
            lor=getcolor(tx,ty);
            cur=getchess(sx,sy);
            eat=getchess(tx,ty);
            if(lor=="empty")    lor="";
            if(eat=="empty")    eat="NA";
            moving(sx,sy,tx,ty);
            if(checkgoi()!="not")    goi="yes";
            else    goi="no";
            if(checkove())
            {
                over=1;
                ove="yes";
            }
            else    ove="no";
            cur=final(cur);
            res.push_back(col+" "+cur);
            if(lor!="") res.push_back(lor+" "+eat);
            else    res.push_back(eat);
            res.push_back(goi);
            res.push_back(ove);
            return res;
        }
    }
    vector<string> moveduck(int sx,int sy,int tx,int ty)
    {
        vector<string> res;
        if(over||!ocduck(sx,sy,tx,ty)||getcolor(sx,sy)!=color)
        {
            res.push_back("Invalid command");
            return res;
        }
        else
        {
            string cur,eat,goi,ove,col,lor;
            col=getcolor(sx,sy);
            lor=getcolor(tx,ty);
            cur=getchess(sx,sy);
            eat=getchess(tx,ty);
            if(lor=="empty")    lor="";
            if(eat=="empty")    eat="NA";
            moving(sx,sy,tx,ty);
            if(checkgoi()!="not")    goi="yes";
            else    goi="no";
            if(checkove())
            {
                over=1;
                ove="yes";
            }
            else    ove="no";
            cur=final(cur);
            res.push_back(col+" "+cur);
            if(lor!="") res.push_back(lor+" "+eat);
            else    res.push_back(eat);
            res.push_back(goi);
            res.push_back(ove);
            return res;
        }
    }
    vector<string> movesoldier(int sx,int sy,int tx,int ty)
    {
        vector<string> res;
        if(over||!ocsoldier(sx,sy,tx,ty)||getcolor(sx,sy)!=color)
        {
            res.push_back("Invalid command");
            return res;
        }
        else
        {
            string cur,eat,goi,ove,col,lor;
            col=getcolor(sx,sy);
            lor=getcolor(tx,ty);
            cur=getchess(sx,sy);
            eat=getchess(tx,ty);
            if(lor=="empty")    lor="";
            if(eat=="empty")    eat="NA";
            moving(sx,sy,tx,ty);
            if(checkgoi()!="not")    goi="yes";
            else    goi="no";
            if(checkove())
            {
                over=1;
                ove="yes";
            }
            else    ove="no";
            cur=final(cur);
            res.push_back(col+" "+cur);
            if(lor!="") res.push_back(lor+" "+eat);
            else    res.push_back(eat);
            res.push_back(goi);
            res.push_back(ove);
            return res;
        }
    }
    vector<string> execute(int sx,int sy,int tx,int ty)
    {
        if(getchess(sx,sy)=="captain")    return movecaptain(sx,sy,tx,ty);
        else if(getchess(sx,sy)=="guard")    return moveguard(sx,sy,tx,ty);
        else if(getchess(sx,sy)=="elephant")    return moveelephant(sx,sy,tx,ty);
        else if(getchess(sx,sy)=="horse")    return movehorse(sx,sy,tx,ty);
        else if(getchess(sx,sy)=="car")    return movecar(sx,sy,tx,ty);
        else if(getchess(sx,sy)=="duck")    return moveduck(sx,sy,tx,ty);
        else if(getchess(sx,sy)=="soldier")    return movesoldier(sx,sy,tx,ty);
        else    return vector<string>({"Invalid command"});
    }
}redplay,blueplay;
void mapinitial()
{
    evemap.resize(20);
    static vector<string> zero({"red-car","red-horse","red-elephant","red-guard","red-captain","red-guard","red-elephant","red-horse","red-car"});
    static vector<string> one({"empty","empty","empty","empty","empty","empty","empty","empty","empty"});
    static vector<string> two({"red-duck","empty","empty","empty","empty","empty","empty","empty","red-duck"});
    static vector<string> three({"red-soldier","empty","red-soldier","empty","red-soldier","empty","red-soldier","empty","red-soldier"});
    static vector<string> four({"empty","empty","empty","empty","empty","empty","empty","empty","empty"});
    static vector<string> five({"empty","empty","empty","empty","empty","empty","empty","empty","empty"});
    static vector<string> six({"blue-soldier","empty","blue-soldier","empty","blue-soldier","empty","blue-soldier","empty","blue-soldier"});
    static vector<string> seven({"blue-duck","empty","empty","empty","empty","empty","empty","empty","blue-duck"});
    static vector<string> eight({"empty","empty","empty","empty","empty","empty","empty","empty","empty"});
    static vector<string> nine({"blue-car","blue-horse","blue-elephant","blue-guard","blue-captain","blue-guard","blue-elephant","blue-horse","blue-car"});
    evemap[0]=zero;
    evemap[1]=one;
    evemap[2]=two;
    evemap[3]=three;
    evemap[4]=four;
    evemap[5]=five;
    evemap[6]=six;
    evemap[7]=seven;
    evemap[8]=eight;
    evemap[9]=nine;
    for(int i=0;i<evemap.size();++i)    evemap[i].resize(20);
}
int main()
{
//     freopen("duck.in","r",stdin);
//    freopen("own.out","w",stdout);
    mapinitial();
    redplay.color="red";
    blueplay.color="blue";
    int q,now=1;
    scanf("%d",&q);
//    printmap();
    for(int i=1;i<=q;++i)
    {
        int sx,sy,tx,ty;
        scanf("%d%d%d%d",&sx,&sy,&tx,&ty);
//        printf("{%d %d %d %d}\n",sx,sy,tx,ty);
        vector<string> ret;
        if(now&1)    ret=redplay.execute(sx,sy,tx,ty);
        else    ret=blueplay.execute(sx,sy,tx,ty);
        if(ret[0]=="Invalid command")    printf("Invalid command\n");
        else
        {
            printf("%s;%s;%s;%s\n",ret[0].c_str(),ret[1].c_str(),ret[2].c_str(),ret[3].c_str());
            if(ret[3]=="yes")    over=1;
            now++;
        }
//         if(i>=q-1)
//         printmap();
    }
    return 0;
}

Solution Set -「ARC 111」

15-01-2021
笔记
0 comment

「ARC 111A」Simple Math 2

Link.

$\lfloor \frac{10^N - kM^2}{M} \rfloor \equiv \lfloor \frac{10^N}{M} - kM \rfloor \equiv \lfloor \frac{10^N}{M} \rfloor - kM \equiv \lfloor \frac{10^N}{M} \rfloor \pmod M (k \in \mathbb{Z})$

#include <iostream>

using i64 = long long;

int cpow ( int bas, i64 idx, const int p ) {
    int res = 1;
    while ( idx ) {
        if ( idx & 1 )    res = ( i64 )res * bas % p;
        bas = ( i64 )bas * bas % p, idx >>= 1;
    }
    return res;
}

int main () {
    std::ios::sync_with_stdio ( 0 ); std::cin.tie ( 0 ); std::cout.tie ( 0 );
    i64 n; int m; std::cin >> n >> m;
    std::cout << ( cpow ( 10, n, m * m ) / m ) % m << '\n';
    return 0;
}

「ARC 111B」Reversible Cards

Link.

nowcoder 原题。

#include<cstdio>
int n,cab[400010],fa[400010],a,b,ans;
int findset(int x)
{
    if(fa[x])    return fa[x]=findset(fa[x]);
    else    return x;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
    {
        scanf("%d%d",&a,&b);
        a=findset(a);
        b=findset(b);
        if((a^b)&&(!cab[a]||!cab[b]))
        {
            fa[a]=b;
            cab[b]|=cab[a];
            ans++;
        }
        else if(!cab[a])
        {
            cab[a]=1;
            ans++;
        }
    }
    printf("%d\n",ans);
    return 0;
}

「ARC 111C」Too Heavy

Link.

构造出一个操作序列。

先不考虑最小，只考虑构造出来。

参考某道 ABC D 题，直接连边。

$i\rightarrow p_{i}\rightarrow p_{p_{i}}\rightarrow\cdots\rightarrow i$。

$1\ 2$ 分别表示 person、baggage。

再想，相当于我们想要让，$1$ and $2$ 一一对应。

一个 $(u,v)$ 的 $2$（即 $v$）不能被交换只在 $a_{u}\le b_{v}$。

所以无解就是这个环中存在 $a_{u}\le b_{v}$。

剩下构造，先考虑满足规则。

贪心的选一个最大的 $a_{i}$ 进行即可。

#include<queue>
#include<cstdio>
#include<algorithm>
using namespace std;
vector<pair<int,int> > ans;
int n,a[200010],b[200010],p[200010],rev[200010],vis[200010];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i)    scanf("%d",&a[i]);
    for(int i=1;i<=n;++i)    scanf("%d",&b[i]);
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&p[i]);
        rev[p[i]]=i;
    }
    vector<int> per;
    for(int i=1;i<=n;++i)
    {
        if(p[i]^i)
        {
            if(a[rev[i]]<=b[i])
            {
                printf("-1\n");
                return 0;
            }
            if(!vis[i])
            {
                vis[i]=1;
                per.clear();
                per.push_back(i);
                for(int j=p[i];j^i;j=p[j])
                {
                    if(a[rev[j]]<=b[j])
                    {
                        printf("-1\n");
                        return 0;
                    }
                    vis[j]=1;
                    per.push_back(j);
                }
                int pos=0,val=0;
                for(int j=0;j<per.size();++j)
                {
                    if(a[per[pos]]<=a[per[j]])
                    {
                        pos=j;
                        val=per[j];
                    }
                }
                for(int j=pos+1;j<per.size();++j)    ans.push_back(make_pair(val,per[j]));
                for(int j=0;j<pos;++j)    ans.push_back(make_pair(val,per[j]));
            }
        }
    }
    printf("%d\n",ans.size());
    for(int i=0;i<ans.size();++i)    printf("%d %d\n",ans[i].first,ans[i].second);
    return 0;
}

「ARC 111D」Orientation

Link.

像个贪心？

$c_{u}\neq c_{v}$
- $c_{u}>c_{v}$：$\rightarrow$
- $c_{u}<c_{v}$：$\leftarrow$
$c_{u}=c_{v}$

在一个环里，深搜即可。

~~这 C D 放反了吧~~

#include<queue>
#include<cstdio>
#include<string>
#include<algorithm>
using namespace std;
vector<pair<int,int> > e[110];
vector<string> ans;
int n,m,c[110],eve[110][110],vis[110];
void dfs(int x)
{
    vis[x]=1;
    for(int i=1;i<=n;++i)
    {
        if(eve[x][i])
        {
            eve[i][x]=0;
            if(!vis[i])    dfs(i);
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        e[u].push_back(make_pair(v,i));
    }
    for(int i=1;i<=n;++i)    scanf("%d",&c[i]);
    ans.resize(m);
    for(int i=1;i<=n;++i)
    {
        for(int j=0;j<e[i].size();++j)
        {
            int y=e[i][j].first,id=e[i][j].second-1;
            if(c[i]>c[y])    ans[id]="->";
            else if(c[i]<c[y])    ans[id]="<-";
            else    eve[i][y]=eve[y][i]=1;
        }
    }
    for(int i=1;i<=n;++i)
    {
        for(int j=0;j<e[i].size();++j)
        {
            int y=e[i][j].first,id=e[i][j].second-1;
            dfs(i);
            if(eve[i][y])    ans[id]="->";
            else if(eve[y][i])    ans[id]="<-";
        }
    }
    for(int i=0;i<ans.size();++i)    printf("%s\n",ans[i].c_str());
    return 0;
}

「ARC 111E」Simple Math 3

Link.

即求：

$$ \sum_{i=1}^{\infty}[\lfloor\frac{A+B\times i-1}{D}\rfloor=\lfloor\frac{A+C\times i}{D}\rfloor] $$

题目说这玩意儿是 finite，然后（没加思考）跑到 U 群问成功丢人。

悲伤的故事，这告诉我们问前先思考。

原因是 $i$ 大了 $[A+B\times i,A+C\times i]$ 的长度一定 $\ge D$。

具体来说是 $i>\frac{D-2}{C-B}$ 的时候就完了。

那么式子改写为：

$$ \sum_{i=1}^{\frac{D-2}{C-B}}[\lfloor\frac{A+B\times i-1}{D}\rfloor=\lfloor\frac{A+C\times i}{D}\rfloor] $$

继续分析，此时的区间 $[A+B\times i,A+C\times i]$ 的长度小于 $D$，里面最多有一个数是 $D$ 的 multiple。

不会了看题解要类欧不会了抄板子过题了

这种推不复杂考板的题好草人啊。。。。

upd：

official editorial 说可以用 AC lib 的 floor_sum 直接算。

屑行为 details。

#include<cstdio>
int T;
long long a,b,c,d;
long long dfs(long long a,long long b,long long c,long long n)
{
    if(a>=c||b>=c)    return dfs(a%c,b%c,c,n)+(a/c)*(n+1)*n/2+(b/c)*(n+1);
    else if(a==0)    return 0;
    else    return (a*n+b)/c*n-dfs(c,c-b-1,a,(a*n+b)/c-1);
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
        printf("%lld\n",(d-2)/(c-b)-dfs(c,a,d,(d-2)/(c-b))+dfs(b,a-1,d,(d-2)/(c-b)));
    }
    return 0;
}

「ARC 111A」Simple Math 2

Link.

missing。

Solution Set -「ABC 183」

12-01-2021
笔记
0 comment

本来十分抗拒，但 GM 强制。

「ABC 183A」ReLU

Link.

略。

#include<cstdio>
int main()
{
    long long n;
    scanf("%lld",&n);
    printf("%lld\n",n>0?n:0);
    return 0;
}

「ABC 183B」Billiards

Link.

设答案坐标 $A(m,n)$，然后算出 $y_{AG}$ 解析式，再带 $x=S'_{x}$，$S'$ 是 $S$ 关于直线 $x=m$ 的对称点，得出来的 $y$ 要等于 $n$，然后列个方程解出来答案为 $\frac{S_{x}G_{y}+G_{x}S_{y}}{S_{y}+G_{y}}$。

#include<cstdio>
double sx,sy,gx,gy;
int main()
{
    scanf("%lf%lf%lf%lf",&sx,&sy,&gx,&gy);
    printf("%lf\n",(sx*gy+gx*sy)/(sy+gy));
    return 0;
}

「ABC 183C」Travel

Link.

全排列枚举算答案即可。

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
vector<int> per;
int n,ans;
long long k,tim[20][20];
int main()
{
    scanf("%d%lld",&n,&k);
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=n;++j)    scanf("%lld",&tim[i][j]);
    }
    per.resize(n+2);
    for(int i=1;i<=n;++i)    per[i]=i;
    per[n+1]=1;
    do
    {
        long long sum=0;
        for(int i=2;i<=n+1;++i)    sum+=tim[per[i-1]][per[i]];
        if(sum==k)    ++ans;
    }while(next_permutation(per.begin()+2,per.end()-1));
    printf("%d\n",ans);
    return 0;
}

「ABC 183D」Water Heater

Link.

前缀和。

#include<cstdio>
int n,s[200010],t[200010],p[200010],w;
long long dif[200010];
int main()
{
    scanf("%d%d",&n,&w);
    for(int i=1;i<=n;++i)    scanf("%d%d%d",&s[i],&t[i],&p[i]);
    for(int i=1;i<=n;++i)
    {
        dif[s[i]]+=p[i];
        dif[t[i]]-=p[i];
    }
    for(int i=1;i<=200000;++i)    dif[i]+=dif[i-1];
    for(int i=0;i<=200000;++i)
    {
        if(dif[i]>w)
        {
            printf("No\n");
            return 0;
        }
    }
    printf("Yes\n");
    return 0;
}

「ABC 183E」Water Heater

Link.

递推完了。

#include<cstdio>
const int mod=1e9+7;
long long ans;
int n,m,mp[2010][2010],row[2010],col[2010],dia[5010];
char str[2010];
int add(long long a,long long b)
{
    if(a+b>=mod)    return (a+b)%mod;
    else    return a+b;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
    {
        scanf("%s",str+1);
        for(int j=1;j<=m;++j)
        {
            if(str[j]=='.')    mp[i][j]=0;
            else    mp[i][j]=1;
        }
    }
    int lay=2e3;
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=m;++j)
        {
            if(mp[i][j])
            {
                row[i]=0;
                col[j]=0;
                dia[i-j+lay]=0;
            }
            else
            {
                int tmp=add(add(row[i],col[j]),dia[i-j+lay]);
                if(i==1&&j==1)    ++tmp;
                row[i]=add(row[i],tmp);
                col[j]=add(col[j],tmp);
                dia[i-j+lay]=add(dia[i-j+lay],tmp);
                ans=tmp;
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}

「ABC 183F」Confluence

Link.

并查集板。

#pragma GCC diagnostic error "-std=c++11"
#include<map>
#include<cstdio>
using namespace std;
map<int,int> mp[200010];
int n,m,fa[200010];
void makeset()
{
    for(int i=1;i<=n;++i)    fa[i]=i;
}
int findset(int x)
{
    if(x^fa[x])    fa[x]=findset(fa[x]);
    return fa[x];
}
void mergeset(int x,int y)
{
    x=findset(x);
    y=findset(y);
    if(x^y)
    {
        if(mp[x].size()>mp[y].size())
        {
            fa[y]=x;
            for(auto p:mp[y])    mp[x][p.first]+=p.second;
        }
        else
        {
            fa[x]=y;
            for(auto p:mp[x])    mp[y][p.first]+=p.second;
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    makeset();
    for(int i=1;i<=n;++i)
    {
        int x;
        scanf("%d",&x);
        mp[i][x]++;
    }
    while(m--)
    {
        int opt,opx,opy;
        scanf("%d%d%d",&opt,&opx,&opy);
        if(opt==1)    mergeset(opx,opy);
        else
        {
            int tmp=findset(opx);
            printf("%d\n",mp[tmp][opy]);
        }
    }
    return 0;
}

Record -「Tricks」记录

09-01-2021
笔记
0 comment

曼哈顿距离 $\text{dist}(A,B)=|x_{A}-x_{B}|+|y_{A}-y_{B}|$ 可以拆成 $\max\{x_{A}-x_{B}+y_{A}-y_{B},x_{A}-x_{B}-y_{A}+y_{B},-x_{A}+x_{B}+y_{A}-y_{B},-x_{A}+x_{B}-y_{A}+y_{B} \}$。agc 034d
走步数什么的构造题步数限制大约在 $\log$ 级别可考虑二进制拆分（倍增构造）。arc 103b
$x\bmod m$ 除了拆成 $x-\lfloor\frac{x}{m}\rfloor\times m$ 还可以拆成 $x-km,(k\in \mathbb{Z})$。arc 111b
像什么第 $i$ 个人对应第 $p_{i}$ 个物品，$p$ 是 $1,\cdots,n$ 的一个排列这种，直接连边。arc 111c / some abc d
对应上一条，这种情况连边一定是一个这样 $i\rightarrow p_{i}\rightarrow p_{p_{i}}\rightarrow\cdots\rightarrow i$ 的环。arc 111c
一个平面上有一堆点 $(x_{1},m),(x_{2},m),\cdots,(x_{n},m)$（$x_{i}$ 单调递增），找一点 $(n,m)$ 使得 $\sum\text{dist}((x_{i},m),(n,m))$ 最小，则 $n$ 的取值范围是
$[a_{\lfloor\frac{n+1}{2}\rfloor},a_{\lfloor\frac{n+2}{2}\rfloor}]$。cf 1486b
字符串本质不同子串数：$\sum_{i=1}^{n}n-sa_{i}-ht_{i}+1=\sum_{i=1}^ni-ht_i$ / $\sum_{i=0}^{n-1}n-sa_i-ht_i=i+1-ht_i$。bzoj 4310
把字符串反转后插入 SAM 后，两个原串的后缀在 parent tree 上的 LCA 是这两个后缀的 LCP。bzoj 3879
对于树上/图上/序列上数某些个点中满足一些条件的点的个数（像 LCA、重心之类的），考虑一个点能作为满足条件的点几次。plural
我们记一个结点 $u$ 的重儿子为 $hb_{u}$，对于 $\text{subtree}(u)$，如果 $u$ 不是 $\text{subtree}(u)$ 的 centroid，那么 $\text{subtree}(u)$ 的 centroid 一定在 $\text{subtree}(hb(u))$ 里。csp 2019 centroid
根据上一条，我们可以直接倍增找重心（注意只能从根开始找）。csp 2019 centroid
值域比较小的关于值域的一些不等或等量关系的题可以考虑把值域放到指数构造生成函数。hk 2016 a+b problem
$i\times j=\binom{i+j}{2}-\binom{i}{2}-\binom{j}{2}$。loc 28870
答案和阶乘相关的，并且模数长得很怪，比如 $998857459=461\times773\times2803$ 这种，当 $i\ge2803$ 时，$i!\bmod998857459=0$。loc 28853
BST 相关，序列有序，$[l,r]$ 对应 BST 上一棵子树，且其父结点一定是 $l-1$ 或 $r+1$，具体是哪个要看大小讨论。cf 1025d
序列分段可以先考虑平方 DP 再优化。csp 2019 partition / ctsc 2012
有多个关键字的 DS 题可以考虑离线按一个关键字排序。lg p3247
找递推关系可以考虑差分。lg p6156
$low_{y}\leqslant dfn_{x}$ 意味着 $x,y$ 在一个环。plural
$a\&b+a\oplus b=a|b$； $a\&b+a|b=a+b$；$a+b=a\oplus b+2(a\&b)$。cf 1451e1
$fib(n+m)=fib(n+1)fib(m)+fib(n)fib(m-1)$。cf 446c
棋盘向下 / 右走，很有些性质和 $n+m$ 有关，且移动一次 $i+j$ 加一，不会存在移动一次 $i+j$ 还是 $i+j$。同时在一条从右上往左下的对角线上的点 $i+j$ 相同。arc 120b
操作类似于令 $a(i)\leftarrow a(i)-1,a(i+1)\leftarrow a(i+1)+1$ 然后交换 $a(i),a(i+1)$ 的，本质是保证下标，令 $A(i)=a(i)+i$ 可以使问题简化。arc 120c
在 $n$ 个元素中连边如果行不通不妨考虑每个元素内部连边。sgu 101 / abc 209e
有多个元素分别对答案贡献时，如果单个元素的贡献很好算，不妨考虑每个元素的贡献次数。many e.g.　abc 209f
出现 $a\mod p=b\mod p$ 时，等价于 $a-b\equiv0\pmod p$，对应到 $a_i\equiv a_{i+1}\equiv\dots\equiv a_j\pmod p$，就考虑差分。cf 1548b (cf 1549d)
出现形似 $a\times b$ 为完全平方数的限制时，考虑消除平方因子，弱化成 $a=b$。cf 840c
$\gcd(a,b)=\gcd(a+kb,b)$。unknown
$\sum_i\sum_j[(i,j)=x]=\varphi(\lfloor\frac{N}{x}\rfloor)\times2-1$。
当 $(a,b)=1$，$(a^i-b^i,a^j-b^j)=a^{(i,j)}-b^{(i,j)}$。
如果一个函数 $f(x)$ 的 $k$ 阶差分是一个非零常数那么 $f(x)$ 一定是一个 $k$ 次多项式。
若题目为序列的变化，考虑构造终止情况。
dp 刷表看看转移范围是否连续，可以看是否能整体 dp 维护。
同一个图的 MST 每种权值的边的数量是一定的。cf 891c
区间操作考虑差分（指题目中对各种序列的操作，不是那种数据结构题）。cf 1120d
数列全为零等价于差分序列全为零。cf 1634f
判定一个点是否在多边形内可由这个点以任意斜率拉出一条射线，看交点奇偶性。cf 375c
数的出现次数的 mex 可以暴力求。cf 940f
排列题可以放在逆排列里考虑，重新描述问题。wc 2022 rrads
上上一条，不同出现次数的级别是根号，很多时候都可以考虑暴力。cf 1476g
出现概率的和式考虑事件是否独立构造组合意义。cf 1523e
和式 = 某个数，考虑看成某个数个 1 然后分配（精度思维）。hdu 7060

分类 笔记 下的文章

Solution Set -「ARC 109」

「ARC 109A」Hands

「ARC 109B」log

「ARC 109C」Large RPS Tournament

「ARC 109D」L

「ARC 109E」1D Reversi Builder

「ARC 109F」1D Kingdom Builder

Solution -「THUPC 2019」Duckchess

Description

Solution

Solution Set -「ARC 111」

「ARC 111A」Simple Math 2

「ARC 111B」Reversible Cards

「ARC 111C」Too Heavy

「ARC 111D」Orientation

「ARC 111E」Simple Math 3

「ARC 111A」Simple Math 2

Solution Set -「ABC 183」

「ABC 183A」ReLU

「ABC 183B」Billiards

「ABC 183C」Travel

「ABC 183D」Water Heater

「ABC 183E」Water Heater

「ABC 183F」Confluence

Record -「Tricks」记录

分类笔记下的文章