Codeforces Round #231 div2前三题

A题

题目大意：A+B=C，可能正确，可能不正确，然后你可以选择移动1，比如A--，C++或者A++，C--或者不移动也可以。

如果可以便输出可以的解决方案，不可以输出Impossible

经过分析可以得到A+B==C或者A+B==C-2或者A+B==C+2，这样可以通过移动或者不移动平衡，天平的原理。不过移动的时候注意不要让A，B， C变成了0

AC代码：

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         using namespace std; char str[1005]; int main() { int a,b,c; int i,j; while(cin>>str) { int len=strlen(str); a=b=c=0; for(i=0; i
        
         b) { a--; c++; } else { b--; c++; } } else if(a+b==c-2) { flag=1; a++; c--; } if(flag) { for(i=0; i
         
          
 
          
B题，是个模拟题，但是自己却误认为是大数的问题，竟然想到了JAVA，完事儿之后觉得不太可能。
          
题目地址：http://codeforces.com/contest/394/problem/B
          
题目的意思是说，让你找一个p位数，比如是XpXp-1...X1,再给你一个t，使得X1XpXp-1...X2=t*(XpXp-1...X1)，如果找的到，选择最小的XpXp-1...X1。开始自己硬推的公式，把前面的设为y，然后开始的数变为y*10+x，转换之后的值变为x*10^p-1+y，然后方程变成了(y*10+x)*t=x*10^p-1+y，通过移动可以变为
          
(10^p-1-t)*x=(10t-1)*y，然后自己采取的方法是枚举x从1到9，然后求y，看y位数，还有整除..后来搞进去了，就一直在搞大数，后来觉得不太可能，10^1000000这个数为免太大了，最后还是TLE了，这是第一次打Cf用java代码。。
          
第二题，不可能用到大数那么复杂的东西，直接一位一位处理就好了。
          
XpXp-1...X2X1
          
 * t
          
 = X1XpXp-1...X2






          
先枚举X1然后，下面的X2就被算出来，再写上去，依次计算就可以了。
          
详见代码：
          
AC代码：
          
 
          
#include
           
            
#include
            
              #include
             
               #include
              
                #include
               
                 #include
                
                  using namespace std; int a[1000005]; int b[1000005]; int main() { int p,t; int i; int x; while(cin>>p>>t) { int flag=0; for(a[p]=1;a[p]<=9;a[p]++) { memset(b,0,sizeof(b)); for(i=p;i>=2;i--) { b[i]+=a[i]*t; int t1=b[i]%10,t2=b[i]/10; a[i-1]=t1; b[i-1]=t2; } b[1]+=a[1]*t; if(a[p]==b[1]&&a[1]!=0) { flag=1; break; } } if(flag) { for(i=1;i<=p;i++) cout<
                 
                   然后再附上自己TLE的JAVA代码，毕竟写了一个多小时，好久都没碰java了。
                  
 
                  
 
                  
import java.util.*;  
import java.math.*;  

public class Main {
    public static void main(String args[])  
    {  
         Scanner cin = new Scanner(System.in);  
         BigInteger y,q,mq,tq;
         BigInteger res;
         int p,t;
         int x;
         
         while(cin.hasNext())  
         {  
             p=cin.nextInt();  
             t=cin.nextInt();  
             int tmp=10;
             q=BigInteger.valueOf(tmp);
             
             res=BigInteger.ONE;
             q=q.pow(p-1);
             
             mq=BigInteger.valueOf(t);
             q=q.subtract(mq);
             //System.out.println(q);  
             
             
             int flag=0;
             for(x=1;x<=9;x++)
             {
                 tq=q;
                 mq=BigInteger.valueOf(x);
                 //mq=BigInteger.valueOf(10*t-1);
                 tq=tq.multiply(mq);
                 mq=BigInteger.valueOf(10*t-1);
                 /*if(x==7)
                 {
                     System.out.print(tq);  
                     System.out.print( ); 
                    System.out.print(tq.divide(mq));  
                    System.out.print( ); 
                    System.out.print(tq.remainder(mq)); 
                    System.out.println( ); 
                 }*/
                 
                 if(tq.remainder(mq).equals(BigInteger.ZERO))
                 {
                     //System.out.print(hehhe);  
                     y=tq.divide(mq);
                     String ans=y.toString();
                     if(ans.length()==p-1)
                     {
                         flag=1;
                         res=y.multiply(BigInteger.valueOf(10)).add(BigInteger.valueOf(x));
                         break;
                     }
                 }
             }
             
             
             if(flag==1)
             {
                 System.out.println(res);  
                // System.out.println(ans.length());  
             }
             else
             {
                 System.out.println(Impossible);  
             }
         }  
    }  
}
 
                  
 
                  
 
                  
 
 
                  
C题：贪心
 
                  
题目地址：http://codeforces.com/contest/394/problem/C
 
                  
B题写完就只有二十分钟了，C题题面很少，但是还是没读懂。。不该把B题想那么复杂。
 
                  
C题就是有n*m个domino，每个domino有两个球，里面装的0或者1，有n*m个domino现在，可以对这些domino重新放置使得每一纵列的1的最多个数最小。domino内部可以旋转，比如01可以变成10.
 
                  
我们可以先把domino里面有两个1的数出来，计数为p2，一个1的计数为p1,0个1的计数为p0，然后贪心。我们先放11的，一排一排的放，然后放一个1的，这时候两排一起放。先放101010...下面就放010101...不过有一些细节需要注意，比如11的放到哪里了，从哪里开始。细节处理好就ok了，详见代码：
 
                  
AC代码：
 
                  
 
 
                  
#include
                   
                    
#include
                    
                      #include
                     
                       #include
                      
                        #include
                       
                         #include
                        
                          using namespace std; char a[2005][2005]; char tmp[5]; int n,m; void output() { int i,j; for(i=1;i<=n;i++) { for(j=1;j<=2;j++) printf(%c,a[i][j]); for(j=3;j<=2*m;j+=2) printf( %c%c,a[i][j],a[i][j+1]); printf( ); } } int main() { int p2,p1,p0; int i,j; while(cin>>n>>m) { p2=p1=p0=0; //统计个数 for(i=0; i
                         
                          >tmp; if(tmp[0]=='1'&&tmp[1]=='1') p2++; else if(tmp[0]=='0'&&tmp[1]=='0') p0++; else p1++; } //cout<
                          
                           0) { for(i=1; i<=n; i++) { for(j=1; j<=2*m; j++) { a[i][j]='1'; t++; if(t==2*p2) { pi=i,pj=j; break; } } if(t==2*p2) break; } } else { pi=0; pj=0; } //cout<