/*当一个人先从自己的内心开始奋斗，他就开始迈向了成功——genies (朝阳的二愣子)*/

HGOI寒假赛第一场，欢迎来自各种学校的各式各样的巨老233333

感觉自己好渺小。还是NOIP （pj）的模拟题吧，也有AK的，不过我是下划线开头，所以我来讲咯。

踩了std，（还有xyc大佬踩了标程！他比我快！），感觉还是挺水的。

自己还是要提高（下午讲了数论，相信高一党没怎么听懂23333）

T1 

solution：就是单调栈的题目，由于是数据听说比较强然后打了手写栈！结果就不说了吧（n方tm都能过！）

思路挺简单就是第一遍找第一个右侧比他高的，能量给高的（在弹栈的时候），显然需要维护一个h单调不增的栈，每次插入一个元素的时候弹出元素，

并把弹出元素的能量v累加到即将插入的元素i上，然后正反搞2遍，扫一遍ans就出来了！（我是不会告诉你我这道题打了1h10min的！）

code:

# include
      
       # define int long longusing namespace std;const int N=1e6+10;struct rec{    int h,v;}a[N];int n,ans[N];inline int read(){    int X=0,w=0; char c=0;    while(c<'0'||c>'9') {w|=c=='-';c=getchar();}    while(c>='0'&&c<='9') X=(X<<3)+(X<<1)+(c^48),c=getchar();    return w?-X:X;}struct sta{    int Top;  rec s[N];    sta(){Top=0;}    bool empty() {
    return (Top==0);}    void push(rec x){s[++Top]=x;}    void pop(){ Top--;}    void clear(){ Top=0;};    rec top(){
     return s[Top];} }s;signed main(){    n=read();    for (int i=1;i<=n;i++)         a[i].h=read(),a[i].v=read();    for (int i=1;i<=n;i++) {        if (s.empty()) { s.push(a[i]);  continue; }        while (!s.empty()&&s.top().h
       
        =1;i--) {        if (s.empty()) { s.push(a[i]);  continue; }        while (!s.empty()&&s.top().h
       
      

T2  

solution:思路也是显然的；需要的时间复杂度是O(T * ⁴√x )

考虑一个数y合法（每个质因数出现2次）那么有 √y 每个质因数出现1次！

知道这个结论，对于每一个x，我们在线在（下取整）√x左右偏移step个单位，构造出x‘=（√x+step）²然后在可行的情况下

 最小化| x'² - x |就行，但是需要考虑一个边界问题，什么时候单调，由于√x是下取整，那么√x和√x+1是一对，

如此类推√x-1和√x+2是一对，则有√x-step和√x+step+1是一对，step∈[0,+∞)，这样就有单调性！

还有那个筛素数实际上只要筛到⁴√x 就行了，就是1e5！

# include 
      
       # define int long longusing namespace std;const int N=1e5+10; bool pr[N];int last[N];vector
       
        a;inline int read(){    int X=0,w=0; char c=0;    while(c<'0'||c>'9') {w|=c=='-';c=getchar();}    while(c>='0'&&c<='9') X=(X<<3)+(X<<1)+(c^48),c=getchar();    return w?-X:X;}void getprime(int Lim){    memset(pr,true,sizeof(pr));    pr[0]=pr[1]=false;    for (int i=2;i<=Lim;i++) {        if (!pr[i]) continue;        a.push_back(i);        for (int j=i+i;j<=Lim;j+=i)         pr[j]=false;    }}bool check(int x){    if (x<0) return false;    int p=0,cnt;    for (;;){        int nowprime=a[p];        if (nowprime>x||p==a.size()-1) break;        cnt=0;        while (x%nowprime==0) cnt++,x/=nowprime;         if (cnt>1) return false;        p++;    }    return true;}# define SQR(x) ((x)*(x))int work(int x) {    int base=sqrt(x);    int step=0;     while (true) {        bool g1=check(base+step+1);        bool g2=check(base-step);        if (g1&&g2) {            if (abs(x-SQR(base+step+1))
        
         9) write(x/10);    putchar('0'+x%10); } void writeln(int x){    write(x);   putchar('\n');}signed main(){    getprime(1e5);    int T=read();    while (T--) {        int x=read();        writeln(abs(x-SQR(work(x))));    }    return 0;}
        
       
      

 

T3  

solution：一开始看成状压orz，怎么存不下状态鸭（滑稽），后来发现看错题了。搜索题！

首先需要知道这么一个东西，如果走到这个点(x,y)用掉了c种颜色，然而要走到(n,m)才算成功，

那么之后（从(x,y)走到(n,m)）至少还需要用掉 n-(x-1)+m-(y-1)-1=n-x+m-y+1 种颜色

特殊的，从(1,1)走到(n,m)需要经过n+m-1个格子.

发现这一条性质30%的分数就有了，开局特判k和n,m的关系。若(n+m-1>k)输出0

然后搜索剪枝，顺序需要保证左上角矩阵出现过的元素不能在此格子填写，所以左上角必须搜完，采用从左往右，从上到下的形式搜！

剪枝：

• 可行性：到(x,y)看剩下的颜色够不够即前面用掉c种，那么若(n-x+m-y+1)>k-c那么直接不可以。
• 对偶性：.在填某一个格子时，如果某些颜色在之前没有使用过，那么他们的情况数都是相同的。（如果之前用过就不一定了!）

不要忘记膜

code:

# include 
      
       # define int long longusing namespace std;const int N=1e3+10;const int mo=1e9+7;const int BIT=11; int mp[N][N],f[N][N],num[BIT];int n,m,k;inline int read(){    int X=0,w=0; char c=0;    while(c<'0'||c>'9') {w|=c=='-';c=getchar();}    while(c>='0'&&c<='9') X=(X<<3)+(X<<1)+(c^48),c=getchar();    return w?-X:X;}# define lowbit(x) ((x)&(-x))# define bit_place(x) (trunc(log(x+0.5)/log(2)))int bit_count(int x){    int cc=0;    for (int i=x;i;i-=lowbit(i)) cc++;    return cc;}int dfs(int x,int y){    if (y>m) x=x+1,y=1;    if (x>n) return 1;    f[x][y]=f[x-1][y]|f[x][y-1];    if (n-x+m-y+1>k-bit_count(f[x][y])) return 0;    int qwq=-1,sum=0;    for (int base=(~f[x][y])&((1<
       
        k+1) { puts("0"); return 0;}    for (int i=1;i<=n;i++)     for (int j=1;j<=m;j++)      mp[i][j]=read(),num[mp[i][j]]++;    memset(f,0,sizeof(f));    int tmp=dfs(1,1);    printf("%lld\n",tmp%mo);    return 0;}