HDU 5671 5672 5673 BestCoder Round #81 (div.1) A B C

A Matirx
操作1,2について;
直接行列を交換する必要はなく、行列交換の記録をメモしておくと、ポインタを作って、ポインタが指す行列に従って出力することに相当します.
3,4操作は同じです.
コード:

/* ***********************************************
Author        :angon
************************************************ */
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <stack>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
#define REP(i,k,n) for(int i=k;i<n;i++)
#define REPP(i,k,n) for(int i=k;i<=n;i++)
#define scan(d) scanf("%d",&d)
#define scann(n,m) scanf("%d%d",&n,&m)
#define mst(a,k)  memset(a,k,sizeof(a));
#define LL long long
#define maxn 1005
#define mod 100000007

int a[maxn][maxn];
int n,m,q;
int t1[maxn],t2[maxn],d1[maxn],d2[maxn];//             
int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int T;
    scan(T);
    while(T--)
    {
        scanf("%d%d%d",&n,&m,&q);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                scan(a[i][j]);
        for(int i=0;i<=n;i++) t1[i]=i,d1[i]=0;
        for(int i=0;i<=m;i++) t2[i]=i,d2[i]=0;
        int x,y,f;
        while(q--)
        {
            scanf("%d%d%d",&f,&x,&y);
            if(f==1)
                swap(t1[x],t1[y]);
            else if(f==2)
                swap(t2[x],t2[y]);
            else if(f==3)
                d1[t1[x]]+=y;
            else
                d2[t2[x]]+=y;
        }
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                printf("%d%c",a[t1[i]][t2[j]]+d1[t1[i]]+d2[t2[j]],j==m?'
':' ');
    }
    return 0;
}

B Sting
文字列(i,j)が要求を満たすサブ列である場合、サブ列(i,k)(k>j)も必然的に要求を満たすサブ列である.従って、各左境界iについて、要求を満たすj,ans+=len−jを最小に見つけるだけである.答えです.
私が書いたコードはこすっています.

/* ***********************************************
Author        :angon
************************************************ */
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <stack>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
#define REP(i,k,n) for(int i=k;i<n;i++)
#define REPP(i,k,n) for(int i=k;i<=n;i++)
#define scan(d) scanf("%d",&d)
#define scann(n,m) scanf("%d%d",&n,&m)
#define mst(a,k)  memset(a,k,sizeof(a));
#define LL long long
#define maxn 1000005
#define mod 100000007

char s[maxn];
int vis[30];
int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int T,n;
    scan(T);
    while(T--)
    {
        scanf("%s",s);
        scan(n);
        mst(vis,0);
        int len=strlen(s);
        int cnt=0,i=0;
        LL ans=0;
        for(int j=0;j<len;j++)
        {
            if(vis[s[j]-'a']==0)
            {
                vis[s[j]-'a']=1;
                cnt++;
            }
            int flag=0;
            if(cnt>=n)
            {
                ans+=len-j;
                i++;
                while(s[i]==s[i-1])
                {
                    ans+=len-j;
                    i++;
                }
                for(int k=i+1;k<j;k++)
                {
                    if(s[k]==s[i-1])
                    {
                        flag=1;
                        break;
                    }
                }
                if(!flag)
                {
                    cnt--;
                    vis[s[i-1]-'a']=0;
                }
                else
                   j--;
            }
        }
        printf("%I64d
",ans);
    }
    return 0;
}

他の人のコードを見ました.の

#include<cstdio>  
#include<cstring>  
typedef long long ll;  
using namespace std;  
char str[1000005];  
int main()  
{  
    int T,k,t;  
    ll ans;  
    scanf("%d",&T);  
    int vis[30];  
    int l,r,flag,len;  
    while(T--)  
    {  
        scanf("%s%d",str,&k);  
        l=r=0;//         
        flag=0;  
        ans=0;  
        len=strlen(str);  
        memset(vis,0,sizeof(vis));  
        while(l<=len-k)  
        {  
            while(flag<k&&r<len)  
            {  
                t=str[r]-'a';  
                if(!vis[t])  
                flag++;//    flag       
                vis[t]++;  
                r++;  
            }//   l          
  
            if(flag==k)  
            ans+=len-r+1;//                
  
            t=str[l]-'a';  
            vis[t]--;  
            if(!vis[t])  
            flag--;  
  
            l++;//      
        }  
        printf("%lld
",ans);  
    }  
    return 0;  
}  

C Robot
問題の解説はカトラン数または黙慈金数である.しかし、どうやって作ったのかは言わず、弱さもその実力がこの2つの数を出すことができなかった.2つの解法の良い解釈:
カトラン数の問題解
黙慈金数解法
しかし、もう一つの方法は、組み合わせ数です.
定義は左へ、右へ、不動はそれぞれ操作0、1、2である.全部でn回操作します.問題はn個の位置にこの3個の数を置くことに変わりますが、以下の要求を保証します.
1、1の個数と0の個数は等しい.
2、任意の時刻の左から右への個数が0以上である個数
まずiつの位置を2に選んで、
C(n, i)
;残りのn-i個の位置は、0、1個の数が等しいため、
残りのn−i個の位置の半分を0(または1)、C(n−i、(n−i)/2)に選択する.残りの位置はすべて1(あるいは0)で、更に要求に合わない2の情況を減らします;すべてのiを列挙して、答えを出すことができます
試合の時私はそう思ったが、最後にはできなかった.要求をどのように保証するか分からないからです.
その後takioの巨大なacコードを見て、2番目の要求に対して、彼はこのように書いた.

C ( n, i) * (C (n - i, (n - i) / 2) - C (n - i, (n - i) / 2 - 1) ) ;

次のように理解できます.
まずn-iの位置で(n-i)/2-1個の0を選んで、それから(n-i)/2個の1を順番に挿入して、この時私はもう1つの0を置いていません.私のこの0はいつもあなたを要求に合わない状態にすることができます.
ps:私はこの文を理解して午後理解しました.のやはり正確な解釈を完全に信じさせるほど捕まえられなかった.上の説明はしばらく正しいと思います.の私はこのような解釈だと思っていました.
/*
この一言に対して..!!私は本当に普通のことを考えたわけではありません.の長い間考えていた.の3、4時間はいつもあります.のやっと分かった!なぜC(n-i,(n-i)/2-1)を減算すると、すべての不一致を排除したのか.全体的に合わないのは、0 x x x x x xまたはx x x x x x x x x 1の場合、すなわち、最初のステップは左と最後のステップは右(原点を越えて負の半軸に行ったことを説明する)、最初のステップは左に、ついでに後ろをどう歩いても間違っていて、残りのn-i-1の位置で残りの(n-i)/2-1の0、すなわちC(n-i-1、(n-i)/2-1)を選択します.もしあなたが最後のステップが右に行くならば、前はどのように歩いても間違っていて、前のn-i-1の位置で(n-i)/2の0を選んで、つまりC(n-i-1、(n-i)/2);両者を加算すると、C(n-i-1,(n-i)/2-1)+C(n-i-1,(n-i)/2)=C(n-i,(n-i)/2)が自分の堅持に感動した..泣く.
*/
結局2分もしないうちに自分でひっくり返された.の
コード:

/* ***********************************************
Author        :angon
************************************************ */
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <stack>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
#define REP(i,k,n) for(int i=k;i<n;i++)
#define REPP(i,k,n) for(int i=k;i<=n;i++)
#define scan(d) scanf("%d",&d)
#define scann(n,m) scanf("%d%d",&n,&m)
#define mst(a,k)  memset(a,k,sizeof(a));
#define LL long long
#define maxn 2000005
#define mod 1000000007

LL f[maxn],rf[maxn],inv[maxn];
LL C(int n,int m)
{
    if(n<0 || m>n) return 0;
    return f[n]*rf[m] % mod*rf[n-m] % mod;
}
int main()
{
    inv[0]=inv[1]=1;
    f[0]=f[1]=rf[0]=rf[1]=1;
    for(int i=2;i<=maxn;i++)
    {
        f[i] = f[i-1]*i % mod;
        inv[i] = inv[mod%i]*(mod-mod/i)% mod;
        rf[i] = rf[i-1]*inv[i] % mod;
    }
    int t,n;
    scan(t);
    while(t--)
    {
        scan(n);
        LL ans=0;
        for(int i=n;i>=0;i-=2) //   n - i   
        {
            ans += ( C(n,i) * ( C(n-i,(n-i)/2) - C(n-i,(n-i)/2-1)+ mod ) ) % mod;
        }
        printf("%I64d
",ans % mod);
    }
    return 0;
}

37~42行をもう一度説明しましょう.ここでは逆元の線形求法を用いた.もしあなたがまだ何が逆元なのか分からないなら、逆元は詳しく理解して、私が見た最高の逆元ブログです.
C(n ,m) %M= n !/m !/(n-m) ! %M
n!%を前処理M=f[n]および1/m!%M = rf[m];rf[]の時使った逆元を求めます