matrix_2015_1 138 - ZOJ Monthly, January 2015

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3844

第一个，n个数，每次操作最大数和最小数都变成他们的差值，最后n个数相同时输出此时的值，暴力跑。

 #include<cstdio>

 int main(){

     int t,n,a[];

     while(~scanf("%d",&t)){

         while(t--){

             scanf("%d",&n);

             for(int i=;i<n;i++){

                 scanf("%d",&a[i]);

             }

             while(true){

                 int bid=,sid=;

                 for(int i=;i<n;i++){

                     if(a[bid]<a[i]) bid=i;

                     if(a[sid]>a[i]) sid=i;

                 }

                 if(a[bid]==a[sid]){

                     printf("%d\n",a[sid]);

                     break;

                 }

                 a[bid]=a[sid]=a[bid]-a[sid];

             }

         }

     }

     return ;

 }

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5440

第二个，n个数，每次操作可以任意选两个数把他们变成他们gcd的值。最后问几步能都变成1，且输出每步选的数的下标。方法：先求出n个数的gcd，如果不为1，输出-1.否则一定能变成全1.变的方法是，先用第一个依次和后面的操作，直至第一个数变成1，然后再用第一个数把剩下的非1的都变掉。

 #include<cstdio>

 #include<vector>

 using namespace std;

 const int M=1e5+;

 typedef pair<int,int> pii;

 int a[M];

 int gcd(int a,int b){

     return b?gcd(b,a%b):a;

 }

 vector<pii> ans;

 int main(){

     int n;

     int cas=;

     while(~scanf("%d",&n)){

         for(int i=;i<=n;i++){

             scanf("%d",&a[i]);

         }

         int now=a[];

         for(int i=;i<=n;i++){

             now=gcd(now,a[i]);

         }

         printf("Case %d: ",cas++);

         if(now>){

             puts("-1");

             puts("");

             continue;

         }

         ans.clear();

         for(int i=;i<=n;i++){

             int now=gcd(a[],a[i]);

             a[]=a[i]=now;

             ans.push_back(make_pair(,i));

             if(now==) break;

         }

         for(int i=;i<=n;i++){

             if(a[i]==) continue;

             ans.push_back(make_pair(,i));

         }

         int len=ans.size();

         printf("%d\n",len);

         for(int i=;i<len;i++){

             printf("%d %d\n",ans[i].first,ans[i].second);

         }

         puts("");

     }

     return ;

 }

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5435

第三个，52张牌，没有大小王的，输入几张，那么剩下的就是我们可以使用的，必须全用上，问有几种排列使得字典序小于他输入的。

 #include<cstdio>

 #include<cstring>

 #define mt(a,b) memset(a,b,sizeof(a))

 const int M=;

 typedef long long LL;

 const LL mod=1e9+;

 char a[M];

 int num[M];

 int sheng[M];

 int getval(char c){

     if(c=='A') return ;

     if(c=='J') return ;

     if(c=='Q') return ;

     if(c=='K') return ;

     return c-'';

 }

 int s[M];

 LL jc[M];

 LL INV[M];

 void inv_init() { //初始化%mod的乘法逆元

     INV[]=;

     for(int i=; i<M; i++) {

         INV[i]=INV[mod%i]*(mod-mod/i)%mod;

     }

 }

 int main(){

     inv_init();

     jc[]=;

     for(int i=;i<M;i++){

         jc[i]=jc[i-]*i%mod;

     }

     while(~scanf("%s",a)){

         int la=strlen(a);

         mt(num,);

         int val;

         int ls=;

         for(int i=;i<la;i++){

             if(a[i]==''){

                 val=;

                 i++;

             }

             else{

                 val=getval(a[i]);

             }

             num[val]++;

             s[ls++]=val;

         }

         for(int i=;i<=;i++){

             sheng[i]=-num[i];

         }

         LL ans=;

         for(int i=;i<ls;i++){

             for(int j=;j<s[i];j++){

                 if(sheng[j]==) continue;

                 LL tmp=jc[-ls-i-];

                 for(int k=;k<=;k++){

                     if(sheng[k]==) continue;

                     if(k==j){

                         for(int u=;u<=sheng[k]-;u++){

                             tmp*=INV[u];

                             tmp%=mod;

                         }

                     }

                     else{

                         for(int u=;u<=sheng[k];u++){

                             tmp*=INV[u];

                             tmp%=mod;

                         }

                     }

                 }

                 ans+=tmp;

                 ans%=mod;

             }

             if(sheng[s[i]]){

                 sheng[s[i]]--;

                 int sum=;

                 for(int j=;j<=;j++){

                     sum+=sheng[j];

                 }

                 if(sum==){

                     if(i<ls-) ans++;

                     break;

                 }

                 continue;

             }

             break;

         }

         printf("%lld\n",ans%mod);

     }

     return ;

 }

end

巴特西

matrix_2015_1 138 - ZOJ Monthly, January 2015

最新文章

热门文章