1011:水题。

#include
      
       #define REP(i,a,b) for(int i=a;i<=b;i++)#define MS0(a) memset(a,0,sizeof(a))using namespace std;typedef long long ll;const int maxn=1000100;const int INF=1e9+10;const ll MOD=1e9+7;const double EPS=1e-13;char s[maxn];int n;int cnt[1200];int main(){    //freopen("in.txt","r",stdin);    int T;cin>>T;int casen=1;    while(T--){        printf("Case #%d: ",casen++);        MS0(cnt);        scanf("%s",s+1);        n=strlen(s+1);        REP(i,1,n) cnt[s[i]]=1;        int res=0;        REP(i,0,1100) res+=cnt[i];        printf("%d\n",res);    }    return 0;}
      

1001：水题。

吐槽：在我写这道题之前，队友贡献了4次罚时。。。

#include
      
       #define REP(i,a,b) for(int i=a;i<=b;i++)#define MS0(a) memset(a,0,sizeof(a))using namespace std;typedef long long ll;const int maxn=10001000;const int INF=1e9+10;const ll MOD=1e9+7;const double EPS=1e-13;char s[maxn],t[maxn];int n;int lcm(int a,int b){    return a/__gcd(a,b)*b;}int main(){    //freopen("in.txt","r",stdin);    int casen=1;    while(~scanf("%s",t)){        printf("Case #%d: ",casen++);        n=strlen(t);        REP(i,0,n-1) s[i]=t[n-1-i];        int x=lcm(73,137);        int y=0;        for(int i=n-1;i>=0;i--) y=(y*10+s[i]-'0')%x;        puts(y?"NO":"YES");    }    return 0;}
      

1004：水题，直接排序之后模拟。

吐槽：比赛的时候好多队伍用sum/2水过的。。。

#include
      
       #define REP(i,a,b) for(int i=a;i<=b;i++)#define MS0(a) memset(a,0,sizeof(a))using namespace std;typedef long long ll;const int maxn=1000100;const int INF=1e9+10;const ll MOD=1e9+7;const double EPS=1e-13;int n;int a[maxn];int b[maxn],bn;int main(){    //freopen("in.txt","r",stdin);    int T;cin>>T;int casen=1;    while(T--){        printf("Case #%d: ",casen++);        scanf("%d",&n);        int sum=0;        REP(i,1,n) scanf("%d",&a[i]),sum+=a[i];        if(n==1){            if(a[1]>=2) puts("1");            else puts("0");            continue;        }        sort(a+1,a+n+1);        bn=0;        int st=1;        while(bn
       
        0){                    b[++bn]=a[i],a[i]--;                    if(a[i]==0) st=i+1;                }            }        }        if(bn==sum/2) printf("%d\n",bn);        else{            int res=bn;            REP(i,1,bn){                if(res==sum/2) break;                int tmpA=0,tmpB=0;                if(i>=2&&b[i-1]!=n) tmpA=1;                if(i<=bn&&b[i+1]!=n) tmpB=1;                if(tmpA&&tmpB) res++;            }            printf("%d\n",res);        }    }    return 0;}/**523 211031 2 332 2 1021 1*/
       
      

1002：水题。

x[i]为每个数取或不取，然后根据平方数质因子都为偶数个，列%2的方程然后高斯消元，答案显然为非零解的个数，由于x[i]取值只能为0或1，所以答案为2^自由变元-1。

  1，没有一眼看出是列方程求解的个数，靠队友提醒才想出来。

  2，提交的时候模数写成了722002，贡献了一次罚时。

#include
      
       #define REP(i,a,b) for(int i=a;i<=b;i++)#define MS0(a) memset(a,0,sizeof(a))using namespace std;typedef long long ll;const int maxn=1000100;const int INF=1e9+10;const ll MOD= 1000000007LL;const double EPS=1e-13;ll prime[510];int pn;int n;ll b[maxn];///--const int MAXN=510;int a[MAXN][MAXN];//增广矩阵int x[MAXN];//解集bool free_x[MAXN];//标记是否是不确定的变元ll qpow(ll n,ll k,ll p){    ll res=1;    while(k){        if(k&1) res=(res*n)%p;        n=(n*n)%p;        k>>=1;    }    return res;}inline int gcd(int a,int b){    int t;    while(b!=0)    {        t=b;        b=a%b;        a=t;    }    return a;}inline int lcm(int a,int b){    return a/gcd(a,b)*b;//先除后乘防溢出}/// 高斯消元法解方程组(Gauss-Jordan elimination).(-2表示有浮点数解，但无整数解，///-1表示无解，0表示唯一解，大于0表示无穷解，并返回自由变元的个数)///有equ个方程，var个变元。增广矩阵行数为equ,分别为0到equ-1,列数为var+1,分别为0到var.int Gauss(int equ,int var){    int i,j,k;    int max_r;// 当前这列绝对值最大的行.    int col;//当前处理的列    int ta,tb;    int LCM;    int temp;    int free_x_num;    int free_index;    for(int i=0;i<=var;i++)    {        x[i]=0;        free_x[i]=true;    }    //转换为阶梯阵.    col=0; // 当前处理的列    for(k = 0;k < equ && col < var;k++,col++)    {
     // 枚举当前处理的行.// 找到该col列元素绝对值最大的那行与第k行交换.(为了在除法时减小误差)        max_r=k;        for(i=k+1;i
       
        abs(a[max_r][col])) max_r=i;        }        if(max_r!=k)        {
     // 与第k行交换.            for(j=k;j
        
         = 0; i--)        {            free_x_num = 0; // 用于判断该行中的不确定的变元的个数，如果超过1个，则无法求解，它们仍然为不确定的变元.            for (j = 0; j < var; j++)            {                if (a[i][j] != 0 && free_x[j]) free_x_num++, free_index = j;            }            if (free_x_num > 1) continue;            temp = a[i][var];            for (j = 0; j < var; j++)            {                if (a[i][j] != 0 && j != free_index) temp -= a[i][j] * x[j]%2;                temp=(temp%2+2)%2;            }            x[free_index] = (temp / a[i][free_index])%2; // 求出该变元.            free_x[free_index] = 0; // 该变元是确定的.        }        return var - k; // 自由变元有var - k个.    }    for (i = var - 1; i >= 0; i--)    {        temp = a[i][var];        for (j = i + 1; j < var; j++)        {            if (a[i][j] != 0) temp -= a[i][j] * x[j];            temp=(temp%2+2)%2;        }        while (temp % a[i][i] != 0) temp+=2;        x[i] =( temp / a[i][i])%2 ;    }    return 0;}///--void solve(){    MS0(a);    REP(j,0,n-1){        ll x=b[j];        REP(i,0,pn-1){            ll t=prime[i];            int k=0;            while(x%t==0) x/=t,k^=1;            a[i][j]=k;        }    }    int res=Gauss(pn,n);    //cout<<"res="<
         
          <
          
           >T;int casen=1;    getPrime();    while(T--){        printf("Case #%d:\n",casen++);        scanf("%d",&n);        REP(i,0,n-1) scanf("%I64d",&b[i]);        solve();    }    return 0;}
          
         
        
       
      

1003：比较简单的树dp。

维护4个值，

 down[u]：从u向下走的最大值。

 down2[u]: 从u向下走然后回到u的最大值。

 up[u]: 从u向上走的最大值。

 up2[u]: 从u向上走然后回到u的最大值。

显然答案就是: 先向下走然后回来再向上走，或者先向上走然后回来再向下走， max( down2[u]+up[u]-val[u], up2[u]+down[u]-val[u] )。

down2[u]的维护比较简单: down2[u]= Sum( max(0, down2[v] -w*2) ) .

down[u] 也不难，比如停在子树v上，那么down[u]= max( down[v]-w+(down2[u]-val[u]) -(max(0,down2[v]-w*2)) .     

维护 up2[u]: 向上走到fa[u] ，然后向上走回来再向下走回来，但是向下走回来不能经过子树u，只要用down2[fa[u]]- down2[u] 就行了。

维护 up[u] : 向上走到fa[u], 这时有两种走法，先下后上或先上后下，先下后上的和up2[u]同理，向上后下的则需要判断 down[fa[u]] 所停的子树是否为u，如果是，那么就需要找次大的停，否则直接停在最大的，所以需要维护down的最大的和次大的点，在down的时候顺便维护就行了。当然需要减去down2[u]-2*w。

很简单的一道树dp，比赛的时候由于计算纸刚好用完没把细节写清楚就开始写了，结果多开了两个没用的数组，调了很久没调出来。。。

赛后改为直接枚举fa的子树，避开维护最大和次大，多了个常数，被卡了。回到宿舍在计算纸写清楚细节后很快就A了。。。

#include
      
       #define REP(i,a,b) for(int i=a;i<=b;i++)#define MS0(a) memset(a,0,sizeof(a))using namespace std;typedef long long ll;const int maxn=1000100;const int INF=1e9+10;int n;int val[maxn];struct Node{    int v,w;};vector
       
         G[maxn];int u,v,w;int down[maxn],down2[maxn],up[maxn],up2[maxn];int first[maxn],second[maxn];int fa[maxn],fw[maxn];void dfs(int u,int f,int w){    fa[u]=f;fw[u]=w;    for(int i=0;i
        
         res) res2=res,res=t,second[u]=first[u],first[u]=v;        else if(t>res2) res2=t,second[u]=v;    }    //if(u==3) cout<<"sd2="<
         
          <
          
           down  B:down2->up    A=-fw[u]+Up2(fa[u]);    //if(u==5) cout<<"A="<
           <
            
             >T;int casen=1; while(T--){ scanf("%d",&n); printf("Case #%d:\n",casen++); REP(i,1,n) scanf("%d",&val[i]); REP(i,0,n) G[i].clear(),down[i]=down2[i]=up[i]=up2[i]=-1; REP(i,1,n-1){ scanf("%d%d%d",&u,&v,&w); G[u].push_back((Node){v,w}); G[v].push_back((Node){u,w}); } dfs(1,0,0); REP(i,1,n) Down2(i),Down(i); REP(i,1,n) Up2(i),Up(i); REP(u,1,n) printf("%d\n",max(down2[u]+up[u]-val[u],up2[u]+down[u]-val[u])); //debug(); } return 0;}
            
          
         
        
       
      

1008：简单的计算几何。

依次枚举4个点，在枚举前3个点的时候剪枝一下，然后枚举第4个点直接判断。

判断条件，

　　1, 4点不共面，混合积不为0.

      2, 题目条件.

复杂度n^4，由于n只有两百，且加了剪枝之后很难达到n^4，所以。。。总之就是数据弱。。。

正解应该是：

   枚举两个点，在枚举其它点判断时候在其中垂面上，在中垂面上任选两个点和原来的两个点构成的正四面体一定合法，当然前提是这4点不共面。

  复杂度n^3。不过这种做法避不开double。

今天只写了n^4的，n^3的明天再写。

吐槽：队友给读这题的时候没说n<=200啊。。。我以为n<=1e5。。。坑。。。

#include
      
       #define REP(i,a,b) for(int i=a;i<=b;i++)#define MS0(a) memset(a,0,sizeof(a))using namespace std;typedef long long ll;const int maxn=1000100;const int INF=1e9+10;int n;struct Point{    int x,y,z;    friend Point operator-(Point A,Point B)    {        return {A.x-B.x,A.y-B.y,A.z-B.z};    }    friend ll operator*(Point A,Point B) /// 点乘    {        return A.x*B.x+A.y*B.y+A.z*B.z;    }};Point p[maxn];Point chax(Point A,Point B) /// 叉乘{    return {A.y*B.z-A.z*B.y,A.z*B.x-A.x*B.z,A.x*B.y-A.y*B.x};}ll dist2(Point A,Point B){    ll tx=A.x-B.x,ty=A.y-B.y,tz=A.z-B.z;    return tx*tx+ty*ty+tz*tz;}ll jud(Point A,Point B,Point C){    ll a=dist2(B,C),b=dist2(A,C),c=dist2(A,B);    if(a!=b&&b!=c&&c!=a) return 0;    if(a+b<=c&&b+c<=a&&a+c<=b) return 0;    if(a==b) return a;    if(b==c) return b;    if(c==a) return c;}bool judge(Point A,Point B,Point C,Point D,ll dt){    Point a=A-D,b=B-D,c=C-D;    if(chax(a,b)*c==0) return 0;    ll ab=dist2(A,B),ac=dist2(A,C),ad=dist2(A,D);    ll bc=dist2(B,C),bd=dist2(B,D),cd=dist2(C,D);    int cnt=0;    if(ab==dt) cnt++;    if(ac==dt) cnt++;    if(ad==dt) cnt++;    if(bc==dt) cnt++;    if(bd==dt) cnt++;    if(cd==dt) cnt++;    if(cnt<4) return 0;    if(cnt==5||cnt==6) return 1;    if(ab!=dt&&cd!=dt) return 1;    if(ac!=dt&&bd!=dt) return 1;    if(ad!=dt&&bc!=dt) return 1;    return 0;}int main(){    freopen("in.txt","r",stdin);    int T;cin>>T;int casen=1;    while(T--){        scanf("%d",&n);        REP(i,1,n) scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].z);        ll res=0;        REP(a,1,n){            REP(b,a+1,n){                REP(c,b+1,n){                    ll dt=jud(p[a],p[b],p[c]);                    if(dt==0) continue;/// 如果3条边都不相等                    REP(d,c+1,n){                        if(judge(p[a],p[b],p[c],p[d],dt)) res++;                    }                }            }        }        printf("Case #%d: %I64d\n",casen++,res);    }    return 0;}
      

1007：待补。

1009：待补。

1010：待补。

 

总结：

    1， 本来应该是可以6个题的，中间由于计算纸刚好用完了，导致03细节没写清楚，然后一直卡在03，08只知道题意却漏了最关键的数据范围。。。

    2， 感觉这场比赛和单挑没什么区别了，思路也是自己想的，代码也全是自己写的，除了03因为模数写错WA了一次其它都是1A。。。队友的作用就是贡献罚时，误导题意，干扰思路的。

    3， 现在写代码的状态应该算不错了， 主要就是要调整好做题习惯，先想清楚细节再写，写完先测各种边缘数据，其实只要做题习惯好点，单挑拿到名额应该是没有什么问题的。