codeforces#512 Div2

pre过了三题 终测又挂了一题 又掉分了 真的是 太菜了

A-In Search of an Easy Problem

水题 有一个1就是hard

 #include <bits/stdc++.h>
 using namespace std;
 typedef long long int ll; int n; int main()
 {
     while(scanf("%d", &n) != EOF){
         int easy;
         bool flag = false;
         for(int i = ; i < n; i++){
             scanf("%d", &easy);
             if(easy == ){
                 flag = true;
             }
         }
         if(flag){
             printf("HARD\n");
         }
         else{
             printf("EASY\n");
         }
     }
     return ;
 }

B-Vasya and Cornfield

求一下四条边的直线方程 代入点判断即可

 #include <bits/stdc++.h>
 using namespace std;
 typedef long long int ll; int n, d, m;
 struct node{
     int x, y;
 }; int main()
 {
     while(scanf("%d%d%d", &n, &d, &m) != EOF){
         for(int i = ; i < m; i++){
             int x, y;
             scanf("%d%d", &x, &y);
             if(y >= -x + d && y <= -x +  * n - d && y >= x - d && y <= x + d){
                 printf("YES\n");
             }
             else{
                 printf("NO\n");
             }
         }
     }
     return ;
 }

C-Vasya and Golden Ticket

终测挂了的题

求前缀和 对于每一个i看sum[n]是sum[i]的几倍 然后看i之后有没有1-k倍的sum[i]

挂了是因为没判断每个倍数都有 找到一个就输出了

 #include <bits/stdc++.h>
 using namespace std;
 typedef long long int ll; int n;
 char s[];
 int presum[]; int main()
 {
     while(scanf("%d", &n) != EOF){
         memset(presum, , sizeof(presum));
         scanf("%s", s + );
         for(int i = ; i <= n; i++){
             int t = s[i] - '';
             presum[i] = presum[i - ] + t;
         }         bool flag = false;
         if(presum[n] == ){
             printf("YES\n");
             continue;
         }
         //cout<<presum[n]<<endl;
         for(int i = ; i <= n; i++){
             if(presum[i] == ){
                 continue;
             }
             if(presum[n] % presum[i]){
                 continue;
             }
             else{
                 int k = presum[n] / presum[i];
                 if(k == ){
                     flag = true;
                     break;
                 }
                 int t = ;
                 for(int j = i + ; j <= n; j++){
                     if(presum[j] == (t) * presum[i]){
                         //cout<<k<<endl;
                         //cout<<i<<" "<<presum[i]<<endl;
                         //cout<<j<<" "<<presum[j]<<" "<<endl;
                         t++;
                     }
                     if(k == t){
                         flag = true;
                         break;
                     }
                 }
                 if(flag){
                     break;
                 }
             }
         }         if(flag){
             printf("YES\n");
         }
         else{
             printf("NO\n");
         }
     }
     return ;
 }

D-Vasya and Triangle

三角形公式S=(1/2)*(x1y2*1+x2y3*1+x3y1*1-x1y3*1-x2y1*1-x3y2*1) =1/2[x1(y2-y3)+x2(y3-y1)+x3(y1-y2)]

当2*n*m/k不是整数时一定没有解

有一个点一定是原点 否则一定可以将这个三角形平移到原点

剩下两个点一个点的横坐标和另一个点的纵坐标一定是0 因为这样就已经足够取尽n*m/2中的所有整数了

接下来就是如何凑出x2和y3了 使得x2 * y3 = 2 * n * m / k

应该想到的是gcd

假设a = gcd(2 * n, k) 那么S = (2 * n / a) * m / (k / a)

将他们分配一下 x2 = (2 * n / a), y3 = (m * a / k)

如果x2 或 y3超出范围限制了 就考虑把2这个系数挪一下就好了

 #include <bits/stdc++.h>
 using namespace std;
 typedef long long int LL; LL n, m, k; LL gcd(LL a, LL b)
 {
     if(b == )return a;
     return gcd(b, a % b);
 } int main()
 {
     while(scanf("%lld%lld%lld", &n, &m, &k) != EOF){
         if(( * n * m) % k){
             printf("NO\n");
         }
         else{
             LL x1, x2, x3, y1, y2, y3;
             x1 = 0ll; y1 = 0ll; x3 = 0ll; y2 = 0ll;
             LL a = gcd( * n, k);
             //cout<<a<<endl;
             y3 = a * m / k;
             x2 =  * n / a;
             //cout<<x2<<" "<<y3<<endl;
             if(x2 > n || y3 > m){
                 y3 *= ;
                 x2 /= ;
             }
             /*if(n % k == 0){
                 y3 = m;
                 x2 = 2 * n / k;
             }
             else if(m % k == 0){
                 x2 = n;
                 y3 = 2 * m / k;
             }
             else{
                 /*int a = n / gcd(n, k);
                 int b = m / gcd(m, k);
                 if(a * 2 < n){
                     x2 = a * 2;
                     y3 = b;
                 }
                 else if(a * 2 < m){
                     y3 = a * 2;
                     x2 = b;
                 }
                 else if(b * 2 < n){
                     x2 = b * 2;
                     y3 = a;
                 }
                 else if(b * 2 < m){
                     y3 = b * 2;
                     x2 = a;
                 }
             }*/
             printf("YES\n");
             printf("%lld %lld\n", x1, y1);
             printf("%lld %lld\n", x2, y2);
             printf("%lld %lld\n", x3, y3);
         }
     }     return ;
 }