A.Alex and a Rhombus

题意：求第n个图形的正方形个数

思路：答案为2*n*n-2*n+1

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
            
           
          
         
        
       
      

 

B. Nick and Array

题意：给你n个数字（-1e6<=ai<=1e6），每个数都可以变成-ai-1，问你怎么变换使得最后ai的乘积最大

思路1：分类讨论（烦）

　　   讨论了很久结果是错误的，想把一些情况合并起来导致思考有问题，所以以后分类讨论就直接分类，不要合并，增加思维难度

　　   找到一个最小值和最大值，之后根据他们是正数负数还是0分类考虑

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
            
           
          
         
        
       
      

 

思路2：可以得出，正数和0都是操作之后会使积变大，直接反转，如果n是奇数，就找一个最小值反转（by DUP4）

#include 
      
       using namespace std;#define N 100010int n, a[N];int main() {    while (scanf("%d", &n) != EOF) {        for (int i = 1; i <= n; ++i) {            scanf("%d", a + i);            if (a[i] >= 0) {                a[i] = -a[i] - 1;            }        }        if (n & 1) {            int Min = *min_element(a + 1, a + 1 + n);            for (int i = 1; i <= n; ++i) {                if (a[i] == Min) {                    a[i] = -a[i] - 1;                    break;                }            }        }        for (int i = 1; i <= n; ++i) {            printf("%d%c", a[i], " \n"[i == n]);        }    }    return 0;}
      

 

C. Valeriy and Deque

题意：n个数，m次询问，询问第k次操作是第一个数和第二个数是什么，一次操作：将前两个数字的较大者放入队头，将较小者放入队尾。

思路，经过n次操作之后，第一个数必定是最大值，第二个数是一个循环。注意全局变量和局部变量（编译器有毒，好吧使自己太菜了，z没有初始化）

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
            
           
          
         
        
       
      

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
            
           
          
         
        
       
      

 

D. Tolik and His Uncle

题意：从（1,1）开始走完（n*m）地图的每一个点，使得前后两个点形成的向量没有重复，输出路径。

思路：当为1*n的地图时 （1,1）->(1,n) ->(1,2) ->(1,n-1) ->...

           如果为n*m的地图呢，（1,1）->(n,m) ->(1,2) ->(n,m-1) ->...

#include
      
       #define rep(i,a,b) for(int i=a;i<=b;i++)using namespace std;int n,m,a[1010100],b[1010100];int pos1=1,pos2=1,z1=0,z2=0;int main(){    scanf("%d%d",&n,&m);    rep(i,1,n/2)    {        rep(j,1,m)        {            printf("%d %d\n",i,j);            printf("%d %d\n",n+1-i,m+1-j);            }        }     if(n%2==1)    {        printf("%d %d\n",n/2+1,1);        a[1]=1;        rep(i,2,m)        {            if(i%2==0) a[i]=m+1-a[i-1];            else a[i]=m+2-a[i-1];            printf("%d %d\n",n/2+1,a[i]);        }    }}
      

 

E. Serge and Dining Room

题意：有n种菜，和m个人，每个人会买他能支付的一个最贵的菜。

q个询问：

      1.可以改变一个菜的价格，问你m个人过后最贵的菜是多少钱。

      2.可以改变一个人有的钱，问你m个人过后最贵的菜是多少钱。

思路：线段树

如果是一个菜，使区间（1，c[i]）都加1

如果是一个人，使区间（1，c[i]）都减1，

查询单点>0，最右边的值。

 

#include
      
       #define rep(i,a,b) for(int i=a;i<=b;i++)using namespace std;#define ll long longconst int N=3e5+5;int a[N],b[N],t[N],v[3*N],p[N],x[N];int ad[N*10],tree[N*10];int n,m,q,sum;ll rd(){    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;}void init(){    n=rd();m=rd();sum=0;     rep(i,1,n) a[i]=rd(),v[++sum]=a[i];    rep(i,1,m) b[i]=rd(),v[++sum]=b[i];    q=rd();    rep(i,1,q)     {        t[i]=rd();        if(t[i]<=2)        {            p[i]=rd(),x[i]=rd(),v[++sum]=x[i];        }    }    sort(v+1,v+1+sum);    sum = unique(v+1, v + sum+1) - v-1;    rep(i,1,n) a[i] = lower_bound(v+1,v + sum+1,a[i]) -v;    rep(i,1,m) b[i] = lower_bound(v+1,v + sum+1,b[i]) -v;    rep(i,1,q)         if(t[i]<=2)            x[i] = lower_bound(v+1,v + sum+1,x[i]) -v;    //rep(i,1,sum) printf(" %d\n",v[i]);}void down(int rt){    ad[rt*2]+=ad[rt];    ad[rt*2+1]+=ad[rt];    tree[rt*2]+=ad[rt];    tree[rt*2+1]+=ad[rt];    ad[rt]=0;}void upd(int rt,int L,int R,int l,int r,int x){    if(l>R || r
       
        0) return getit(2*rt+1,m+1,r);    else return getit(2*rt,l,m);} int get(){    if(tree[1]>=1) return v[getit(1,1,sum)];    else return -1;}void work(){    rep(i,1,n) add(a[i]);    rep(i,1,m) del(b[i]);    rep(i,1,q)    {        if(t[i]==1)        {            del(a[p[i]]);            a[p[i]]=x[i];            add(x[i]);        }        if(t[i]==2)        {            add(b[p[i]]);            b[p[i]]=x[i];            del(x[i]);        }        printf("%d\n",get());    }}int main(){    init();    work();    //outit();    }