1001 Mod, Or and Everything
题意：给你一个n，计算（n mod 1）or (n mod 2) or...or(n mod (n-1)) or (n mod n)。
思路：我们可以发现余数以此为0，1，2，3,...,(n-1)/2,...,3，2，1，0。即包含了0~(n-1)/2中的所有数，由此可以推得答案为,其中是第一个大于(n-1)/2的二次幂。
代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while(t--) {
        ll n; cin >> n;
        ll tmp=(n-1)/2;
        ll ans = 1;
        while(ans <= tmp) {
            ans*=2;
        } 
        cout << ans - 1 << endl;
    } 
    return 0;
}

1005 Minimum spanning tree
题意：一个图中有n-1个点，每个点的权值为2~n，在顶点a和顶点之间连一条边的代价是lcm(a,b)，计算将所有点连成一个树的最小代价。
思路：所有质数都连接到2上来，所有合数都连接到它的最小质因数上。
代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 10000000+5; 
ll sum[N];
ll st[N],prime[N],cnt;
ll vis[N];
void ola() {
    for(int i=2;i<=10000000;i++) {
        if(!st[i]) prime[++cnt]=i;
        for(int j=1;j<=cnt&&i*prime[j]<=10000000;j++) {
            st[i*prime[j]]=1;
            vis[i*prime[j]]=i;
            //vis[i*prime[j]]=i;
            //cout << "ceshi : " << i*prime[j] << " " << i << endl;
            if(i%prime[j]==0) {
                break;
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int t; cin >> t;ola();
    for(int i=3;i<=N;i++) {
        if(st[i]==0) sum[i]=sum[i-1]+i*2;
        else sum[i]=sum[i-1]+i;
    }
    while(t--) {
        int n; cin >> n;
        cout << sum[n] << endl;
    } 
    return 0;
}

1008 Maximal submatrix
题意：给你一个n*m的矩阵，输出每列不递减的最大面积子矩阵的面积。
思路：我们先对每一列的值进行一个处理，如果当前位置的值小于上一个位置的值我们令它为1，否则为上一个+1。例如某一列的值为2，3，5，4，5，6，那么处理完之后应该为1，2，3，1，2，3，这样我们就得到了这一列到该元素的一个不递减长度。最后循环每行，判断一下连续个数。注意不要忘记将算出来的答案与m相比。
代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 2e3+5;
int a[N][N],h[N][N];
int main()
{
    int t; scanf("%d",&t);
    while(t--) {
        int n,m; scanf("%d %d",&n,&m);
        for(int i=1;i<=n;i++) {
            for(int j=1;j<=m;j++) {
                scanf("%d",&a[i][j]); 
            }
        }
        for(int i=1;i<=n;i++) {
            for(int j=1;j<=m;j++) {
                if(i==1||a[i][j]<a[i-1][j]) {
                    h[i][j]=1;
                }
                else h[i][j]=h[i-1][j]+1;
            }
        }
        int cnt=0,minn=n,ans=0;
        for(int i=1;i<=n;i++) {
            for(int j=1;j<=m;j++) {
                if(h[i][j]!=1) {
                    cnt++;
                    minn=min(minn,h[i][j]);
                    if(j==m&&cnt) {
                        ans=max(ans,minn*cnt);
                        cnt=0;
                        minn=N;
                    }
                }
                else {
                    ans=max(ans,minn*cnt);
                    cnt=0;
                    minn=n;
                }
            }
        }
        printf("%d\n",max(ans,m));
    }
    return 0;
}

1009 KD-Graph
题意：n个点，m条边，将n个点严格分为k组。是否存在一个最小的D值恰好使原图变为k个连通的部分。题目中连通的定义：
①对于任意一组，组内的顶点两两之间至少存在一条权值小于等于w的路径
②对于任意两组，组间的顶点两两之间不存在任何一条权值小于等于w的路径
思路：将权值按照从小到大排序，用now记录当前组数，取出相同权值的所有边，将这些边的顶点用并查集两两合并，没合并一次组数now-1，因为每合并一次独立的顶点就少了一个，同时记录此时的权值ans，当枚举到下一阶段时，此时边权与上次不一样，判断此时now的值，如果等于k，则输出此时的ans。
赛后补这道题wa了十多次，结果改用C++，t了，再改scanf，过了。。。跟六月份打CCPC正好反过来，当时有一道题用C++一直wa,改用G++就a了。。。
代码：

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1e6+10;
struct node{
    int u,v,c;
}p[N];
int fa[N];
bool cmp(node x, node y) 
{
    return x.c<y.c;
}
int get(int x) {
    return fa[x]==x?fa[x]:fa[x]=get(fa[x]);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int t; scanf("%d",&t);
    while(t--) {
        int n,m,k;scanf("%d %d %d",&n,&m,&k);
        for(int i=1;i<=n;i++) fa[i]=i;
        for(int i=1;i<=m;i++) {
            scanf("%d %d %d",&p[i].u,&p[i].v,&p[i].c);
        }
        sort(p + 1, p + 1 + m, cmp);
        int now=n,ans=0;
        bool flag=false;
        for(int i=1;i<=m;i++) {
            if(p[i].c!=p[i-1].c) {
                if(now==k) {
                    break;
                }
            }
            int x=get(p[i].u);
            int y=get(p[i].v);
            if(x==y) continue;
            now--;
            fa[x]=y;
            ans=p[i].c;
        }
        if(now==k) cout << ans << endl;
        else cout << -1 << endl;  
    }
    return 0;
 }