ACdream 速攻组~-白红宇

ACdream 速攻组~

阅读量：5234 次

发布时间：2019-06-14

本文共 7631 字，大约阅读时间需要 25 分钟。

1007 a + b

1 /*这题就是一个快速幂，但是十分猥琐的是，模是1e10 + 7，不是1e9 + 7，这就产生了一个爆long long的问题。所以要对快速幂中的乘法操作进行一下改造。请教了BIT_Is_a_Tree，学会了传说中的 「快速加」。原理和快速幂一模一样，a^{b}是b个a相乘，a \times b就是b个a相加。缺点是多了\log{n} 的复杂度。 2 */ 3 using namespace std; 4 typedef long long ll; 5 #define MOD 10000000007LL 6 ll fMul(ll a, ll b) { 7     ll t = 0, y = a; 8     while(b) { 9         if(b & 1) t = (t + y) % MOD;10         y = (y + y) % MOD;11         b >>= 1;12     }13     return t;14 }15 ll modExp(ll a, ll b) {16     ll t = 1, y = a;17     while(b) {18         if(b & 1) t = (fMul(t, y)) % MOD;19         y = (fMul(y, y)) % MOD;20         b >>= 1;21     }22     return t;23 }24 int main() {25     int T;26     ll n, k, t, sum;27     cin >> T;28     while(T--) {29         cin >> n >> k;30         sum = 0;31         for(int i = 1; i <= n; i++) {32             cin >> t;33             t = ((t % MOD) + MOD) % MOD;34             sum += modExp(t, k);35             sum %= MOD;36         }37         cout << sum << endl;38     }39     return 0;40 }

View Code

1008 A Very Easy Triangle Counting Game

1 /*题意：在圆上取n个点，相邻两个点之间连线，（注意，n和1相邻），然后所有点对（i ，i+2）相连，问能形成的不同的三角形有多少个？ 2  3 思路：画图找规律，发现n=3,cnt=1;  n=4,cnt=8; n=5 cnt=35  (5*2+5*2+ 5+5+5); n=6 cnt= 32 (6*2+6*2+ 6+2); 4  5         n=7,cnt=35(7*2+7*2+7); n=8, cnt=40(8*2+8*2+8) 发现后面项演变成多边形了！ 6  7      于是得到规律：n>6;cnt=5*n 8 */ 9 #include 
      
         10     int a[7]={
    0,0,0,1,8,35,32};  11     int main()  12     {  13         int T,n,ans;  14         scanf("%d",&T);  15         for(int i=1;i<=T;i++)  16         {  17             scanf("%d",&n);  18             ans=n>6?(5*n):a[n];  19             printf("Case #%d: %d\n",i,ans%20121111);  20         }  21         return 0;  22     }

View Code

1013 Count It!

1 /* 2 扫一遍，胡乱暴力一发~ 3 */ 4 #include
      
        5 #include
       
         6 #include
        
          7 #include
         
           8 #include
          
            9 #include
           
            10 #include
            
             11 #include
             
              12 #include
              
               13 #include
               
                14 #include
                15 #include
                 
                  16 #include
                  
                   17 using namespace std;18 int main()19 {20 int a;21 while(cin>>a)22 {23 string b;24 cin>>b;25 int minn=0;26 for(int i=0;i

View Code

1020 The Game about KILL

1   /* 2 约瑟夫环，n太大，首先可以想到打表找看有没有规律 3  4 可以发现时有规律的 5  6 可以看到，只要是2的i次幂，那么存活的是1，后面的依次加2 7  8 例如4为1,5就是3,6->5,7->7,8->1 9 --------------------------------------------------------10 我直接拍log(n)/log(2)，使劲wa，唉唉唉，姿势长傻了，没办法11 */12  #include 
      
         13     #include 
       
          14     #include 
        
           15     using namespace std;  16     #define ll long long  17     ll f[50],n;  18        19     int main()  20     {  21         int i;  22         f[0] = 1;  23         for(i = 1; i<31; i++)  24             f[i] = f[i-1]*2;  25         while(~scanf("%lld",&n))  26         {  27             for(i = 1; i<31; i++)  28             {  29                 if(n

View Code

1037 UUZ is hunger

1 /* 2 sort一下，然后累加暴力一发~ 3 */ 4 #include
      
        5 #include
       
         6 #include
        
          7 #include
         
           8 #include
          
            9 #include
           
            10 #include
            
             11 #include
             
              12 #include
              
               13 #include
               
                14 #include
                15 #include
                 
                  16 #include
                  
                   17 using namespace std;18 long long a[100010];19 int main()20 {21 long long n,k;22 while(scanf("%lld%lld",&n,&k)!=EOF)23 {24 memset(a,0,sizeof(a));25 long long sum=0;26 int ans=0;27 for(int i=0;i
                   
                    >a[i];29 sort(a,a+n);30 for(int i=n-1;i>=0;i--)31 {32 sum+=a[i];33 ans++;34 if(sum>=k)35 break;36 }37 cout<
                    
                     <

View Code

1061 郭式树

1 /* 2 啪啪啪，叫你别用cin，叫你别用cout，叫你沙茶 3 */ 4     #include 
      
          5     #include 
       
           6     #include 
        
            7     using namespace std;   8         9     int main()  10     {  11         int t;  12         long long x, y;  13         unsigned long long z;  14         scanf("%d", &t);  15         while(t--)  16         {  17             scanf("%lld%lld", &x, &y);  18             if(x > y)  19                 z = x - y;  20             else  21                 z = y - x;  22             printf("%llu\n", z);  23         }  24         return 0;  25     }

View Code

1064 完美数

1   /* 2 数位DP，乱搞一发 3 s=0表示既不含3也不含8 4 s=1表示只含3 5 s=2表示只含8 6 s=3表示既含3也含8 7 */ 8 #include
      
          9     #include
       
          10     int a[10],f[10][4];  11     int new_s(int s,int d){  12         if(d==3)return s|1;  13         if(d==8)return s|2;  14         return s;  15     }  16     int dfs(int i,int s,bool e){  17         if(i==-1)return s==1||s==2;  18         if(!e&&f[i][s]!=-1)return f[i][s];  19         int res=0,u=e?a[i]:9,d;  20         for(d=0;d<=u;d++)res+=dfs(i-1,new_s(s,d),e&&(d==u));  21         return e?res:f[i][s]=res;  22     }  23     int cal(int n){  24         int i=0;  25         while(n){a[i++]=n%10,n/=10;}  26         return dfs(i-1,0,1);  27     }  28     int main(){  29         int T,l,r;  30         scanf("%d",&T);  31         memset(f,-1,sizeof(f));  32         while(T--){  33             scanf("%d%d",&l,&r);  34             printf("%d\n",cal(r)-cal(l-1));  35         }  36         return 0;  37     }

View Code

1065 同心树

1 /* 2 几何题目，乱搞就是 3 */ 4 #include
      
        5 #include
       
         6 #include
        
          7 #include
         
           8 #include
          
            9 using namespace std;10 int main( )11 {12     int T;13     double N,a;14     scanf("%d",&T);15     while( T-- ){16     scanf("%lf%lf",&N,&a);17     if( a >= 90 )18         a -= 90;19     if( a == 0 )20     {21         printf("%.2lf\n",N*N);22         continue;23     }24     a = a*3.141592654/180.0;25     double r = N/( 1 + cos(a) + sin(a) );26     printf("%.2lf\n",N*N-r*r*(sin(2*a)));27     }28     return 0;29 }

View Code

1069 无耻的出题人

1 /*题意：翻译题目之后，再解决翻译之后的题目 2 思路：斐布拉契数，注意规律， 3 翻译代码如下： 4 #include
      
        5 #include
       
         6 char s[28]={'0','a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'}; 7 int main() 8 { 9   long long a[100];10   a[0]=1;a[1]=1;11   for(int i=2;i<100;i++)12     a[i]=a[i-1]+a[i-2];13   char c[100];14   gets(c);15   for(int i=0,x=0;i
        
         37 #include 
         
          38 int main()39 {40   char s[100];41   while(scanf("%s",s)!=EOF)42   {43     int sum=0;44     for(int i=0;s[i];i++)45     {46       if(s[i]>='0' && s[i] <='9')47         sum+=s[i]-'0';48     }49     printf("%d\n",sum);50   }51 }

View Code

1088 哼！我才是最短的

1 /* 2 输出的时候，按照8 1 7 2 6 3 5 4这种一大一小输出即可 3 */ 4     #include
      
          5     #include
       
           6     using namespace std;   7     #define M 1000005   8     #define MN 100000   9     int main()  10     {  11         int n,a;  12         int i,j;  13         cin>>n;  14         while(n--)  15         {  16             cin>>a;  17             if(a%2==0)  18             {  19                 for(i=0,j=1;i

View Code

1125 ACfun

1 /* 2 题意：找到最长的连续A的个数n，然后输出n+1个A 3 思路：暴力。 4 */ 5 #include
      
        6 #include
       
         7 #include
        
          8 using namespace std; 9 int main()10 {11  char s[1001];12  int i,j,k,l,t;13  int sum,max;14  cin>>t;15  getchar();16  while(t--)17  {18    sum=max=0;19    gets(s);20    for(i=0;i
         
          max)30        max=sum;31        if(s[i]!=s[j])32        {33          sum=1;34          break;35        }36      }37      }38    }39    for(i=0;i<=max;i++)40      printf("A");41    printf("\n");42  }43  return 0;44 }