01     签到的

#include
      
       using namespace std;#pragma comment(linker, "/STACK:102400000,102400000")#define rep(i,a,b) for (int i=a; i<=b; ++i)#define per(i,b,a) for (int i=b; i>=a; --i)#define mes(a,b)  memset(a,b,sizeof(a))#define INF 0x3f3f3f3f#define MP make_pair#define PB push_back#define fi  first#define se  secondtypedef long long ll;const int N = 200005;int main(){    int n, cas=0;    while(~scanf("%d", &n))    {        printf("Case #%d: %d\n", ++cas, (int)(log10(2)*n));    }    return 0;}
      

02     模拟

记：sort 比较函数cmp，如果最后相等，应该返回 false，否则会错。。

#include
      
       using namespace std;#pragma comment(linker, "/STACK:102400000,102400000")#define rep(i,a,b) for (int i=a; i<=b; ++i)#define per(i,b,a) for (int i=b; i>=a; --i)#define mes(a,b)  memset(a,b,sizeof(a))#define INF 0x3f3f3f3f#define MP make_pair#define PB push_back#define fi  first#define se  secondtypedef long long ll;const int N = 100000+200, mod = 1e9+7;string s[N];bool is[27];int n, mx[27];ll  num[27][N];struct Str { string si; int len, id; } str[27];void Init(){    mes(num,0);  mes(is, 0);}bool cmp(Str a, Str b){    if(a.len!=b.len) return a.len < b.len;    for(int j=a.len-1; j>=0; j--) if(a.si[j]!=b.si[j]) {        if(a.si[j] < b.si[j]) return true;        if(a.si[j] > b.si[j]) return false;    }    return false;   //    //string s1=a.si, s2=b.si;    //reverse(s1.begin(),s1.end()), reverse(s2.begin(),s2.end());    //return s1
       
        >=1)if(b&1)ans=ans*a%mod; return ans; }int main(){    int cas=0;    while(~scanf("%d", &n))    {        Init();        rep(i,1,n) {            cin>>s[i];            if(s[i].length()!=1) is[s[i][0]-'a']=1;        }        mes(mx, 0);        rep(i,1,n) {            int len=s[i].length();            for(int j=len-1; j>=0; --j)            {                int ch = s[i][j]-'a';                ++num[ch][len-j-1];                mx[ch] = max(mx[ch], len-j);            }        }        rep(i,0,25) {            int len=0;            str[i].si="";            for(int j=0; j
        
         i ? i+1 : i);            for(int j=0; j
        
       
      

03     树形dp，好题

题意： 求一棵树上所有路径不同权值个数的和。

tags： 看了题解才做出来。。

官方题解：单独考虑每一种颜色，答案就是对于每种颜色至少经过一次这种的路径条数之和。反过来思考只需要求有多少条路径没有经过这种颜色即可。直接做可以采用虚树的思想（不用真正建出来），对每种颜色的点按照 dfs 序列排个序，就能求出这些点把原来的树划分成的块的大小。这个过程实际上可以直接一次 dfs 求出。

直观地说，对于每种颜色，假设它在所有路径中都出现，即 n*(n-1)/2次，再减去它没有出现过的路径数量就是答案。 然后它没有出现过的路径数量怎么算呢？  对于每种颜色，把它出现的地方在树上标出，发现它会把树划分成多个块，而在每个块中它是没有出现的，所以就转化成了求每种颜色划分出来的各个块的大小。 各个块的大小该怎么求呢？ 这里就是树dp 来实现了。

设sum[i]为已经dfs遍历过的点中,以颜色i 的点为根的子树的节点个数之和。当dfs遍历到节点 u 时，对于它的一个儿子节点 to，先进入 to 进行dfs。如果子树 to 中有颜色col[u]的点，sum[col[u]] 就会跟着变化。假设 sum[col[u]] 增加了num， 那么节点 to 下面就应该有 size[to]-num个颜色不为 col[u]的点还没有计算过，即 to 连着的块大小为 tmp=size[to]-num，把 tmp*(tmp-1)/2 加入到答案。 然后 sum[col[u]] += tmp 进行维护即可。

#include
      
       using namespace std;#pragma comment(linker, "/STACK:102400000,102400000")#define rep(i,a,b) for (int i=a; i<=b; ++i)#define per(i,b,a) for (int i=b; i>=a; --i)#define mes(a,b)  memset(a,b,sizeof(a))#define INF 0x3f3f3f3f#define MP make_pair#define PB push_back#define fi  first#define se  secondtypedef long long ll;const int N = 200005;int n, col[N], head[N<<1], tot, Size[N], cnt;bool vis[N];ll  sum[N], ans;struct Edge{
    int to,next; } e[N<<1];void Addedge(int u,int v) {e[tot]={v,head[u] }; head[u]=tot++; }void dfs(int u, int fa){    Size[u]=1;    for(int i=head[u]; i!=-1; i=e[i].next) if(e[i].to!=fa)    {        ll  s=sum[col[u]];        dfs(e[i].to, u);        Size[u] += Size[e[i].to];        ll  num=sum[col[u]]-s, tmp=Size[e[i].to]-num;        ans += tmp*(tmp-1)/2, sum[col[u]] += tmp;    }    ++sum[col[u]];}void Init(){    mes(head, -1);  mes(sum, 0);  mes(Size, 0);    ans = 0, tot = 0;    mes(vis, 0);  cnt=0;}int main(){    int cas=0;    while(~scanf("%d", &n))    {        Init();        rep(i,1,n) {            scanf("%d", &col[i]);            if(vis[col[i]]==0) vis[col[i]]=1, ++cnt;        }        int a, b;        rep(i,1,n-1) {            scanf("%d %d", &a, &b);            Addedge(a, b);  Addedge(b, a);        }        dfs(1, 0);        rep(i,1,n) if(vis[i] && i!=col[1]) {            ans += 1LL*(n-sum[i])*(n-sum[i]-1)/2;        }        ans = 1LL*cnt*n*(n-1)/2-ans;        printf("Case #%d: %lld\n", ++cas, ans);    }    return 0;}
      

06     置换群

题意：给出两个数组，求满足 f(i)=b[f(a[i])] 关系的f()有多少个。

tags：把b[] 里面的环放入 a[] 里面，然后a[] 的环应该是 b[] 的环的倍数，且一个 a[i]不能对应多个 b[] 。

#include
      
       using namespace std;#pragma comment(linker, "/STACK:102400000,102400000")#define rep(i,a,b) for (int i=a; i<=b; ++i)#define per(i,b,a) for (int i=b; i>=a; --i)#define mes(a,b)  memset(a,b,sizeof(a))#define INF 0x3f3f3f3f#define MP make_pair#define PB push_back#define fi  first#define se  secondtypedef long long ll;const int N = 100005, mod = 1e9+7;bool vis[N];int mx;int cal(ll *a, int len, ll *num){    mes(vis, 0);    int sum=0;    for(int i=0; i
       
        >=1)if(b&1)ans=ans*a%mod; return ans; }int main(){    int cas=0, n, m;    while(~scanf("%d %d", &n, &m))    {        Init();        for(int i=0; i
        
         0; --j) if(num2[j] && i%j==0)            {                ( res += num2[j]*j%mod ) %= mod;            }            ( ans *= (fpow(res,num1[i]) )) %= mod;        }        printf("Case #%d: ", ++cas);        printf("%lld\n", (ans+mod)%mod);    }    return 0;}
        
       
      

08     快排思想，线性复杂度求第 k小

题意：给出 n,m,A,B,C，其中 ABC为3个参数，用这三个参数可以生成n个数a[i] 。有 m个数b[i]，对于每一个b[i]，我们要找出在 a[] 数组中第 b[i]+1 小的数。

tags： T 到死的节奏。。

官方题解：

快速排序思想 ： 设要排序的数组是A[0]……A[N-1]，首先任意选取一个数据（通常选用数组的第一个数）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。

也就是利用快排思想，我们可以快速地把第 k 小的数找出来，而比它小的数都会换到它的左边，比它大的数都会换到它右边。这样就可以依次减少枚举的数量，达到O(n)复杂度。

类似快排思想：

#include
      
       using namespace std;#pragma comment(linker, "/STACK:102400000,102400000")#define rep(i,a,b) for (int i=a; i<=b; ++i)#define per(i,b,a) for (int i=b; i>=a; --i)#define mes(a,b)  memset(a,b,sizeof(a))#define INF 0x3f3f3f3f#define MP make_pair#define PB push_back#define fi  first#define se  secondtypedef  long long  ll;const int N = 10000005;unsigned  a[N], A, B, C, ans[110];int n, m;bool vis[N];void Qsort(int ki, int l, int r){    int i=l, j=r, k=l;    while(i
       
        a[k])        {            swap(a[i], a[k]);   k=i;            break;        }    }    vis[k] = 1;    if(l
        
         >5); x ^= (x<<1);            t=x, x=y, y=z, z=t^x^y;            a[i] = z;        }        int bi;        rep(i,1,m)        {            scanf("%d", &bi);    ++bi;            int l=bi, r=bi;            for(; l>0 && vis[l]==0; --l) ;   ++l;            for(; r<=n && vis[r]==0; ++r) ;  --r;            Qsort(bi, l, r);            ans[i] = a[bi];        }        printf("Case #%d:", ++cas);        rep(i,1,m) printf(" %lu", ans[i]);        puts("");    }    return 0;}
        
       
      

STL中的 nth_element(arr, arr+x, arr+n) 直接排：

#include
      
       using namespace std;#pragma comment(linker, "/STACK:102400000,102400000")#define mes(a,b)  memset(a,b,sizeof(a))#define INF 0x3f3f3f3f#define MP make_pair#define PB push_back#define fi  first#define se  secondtypedef  long long  ll;const int N = 10000005;unsigned  a[N], A, B, C, ans[110];int n, m;pair
       
         b[110];int main(){    int cas=0;    while(~scanf("%d %d %lu %lu %lu", &n, &m, &A, &B, &C))    {        unsigned  x = A, y = B, z = C, t;        for(int i=1; i<=n; ++i)        {            x ^= (x<<16); x ^= (x>>5); x ^= (x<<1);            t=x, x=y, y=z, z=t^x^y;            a[i] = z;        }        for(int i=1; i<=m; ++i)        {            scanf("%d", &b[i].fi);            ++b[i].fi,  b[i].se=i;        }        sort(b+1, b+1+m);        b[m+1].fi=n;        for(int i=m; i>0; --i)        {            if(i!=m && b[i].fi==b[i+1].fi) {   // 没加这个优化就超时了。。                ans[b[i].se] = ans[b[i+1].se];                continue;            }            nth_element(a+1, a+b[i].fi, a+1+b[i+1].fi);            ans[b[i].se] = a[b[i].fi];        }        printf("Case #%d:", ++cas);        for(int i=1; i<=m; ++i) printf(" %lu", ans[i]);        puts("");    }    return 0;}
       
      

11     水

#include
      
       using namespace std;#pragma comment(linker, "/STACK:102400000,102400000")#define rep(i,a,b) for (int i=a; i<=b; ++i)#define per(i,b,a) for (int i=b; i>=a; --i)#define mes(a,b)  memset(a,b,sizeof(a))#define INF 0x3f3f3f3f#define MP make_pair#define PB push_back#define fi  first#define se  secondtypedef long long ll;const int N = 200005;int main(){    int cas=0;    ll  n, k;    while(~scanf("%lld %lld", &n, &k))    {        ll  pos;        if(k<=n) pos=k;        else        {            k -= n;            ll  cnt1=k/(n-1), cnt2=k%(n-1);            if(cnt2==0) pos = cnt1&1 ? n-1 : n;            else pos=cnt2;        }        printf("Case #%d: %lld\n", ++cas, pos);    }    return 0;}