2019.7.12 训练总结

今天的训练一共六道题，训练时间三小时，训练时间内一共做出了一道题，还WA了11次。

反思：1.因为题目没有认真阅读，导致没有正确理解题目，然后一直没写出来，还把心态写炸了。

　　　2.心态问题很严重，已经第二次由于开题不顺，导致正常训练的成绩非常差，这次训练的C题、D题其实都属于简单题系列，D题最后都没来得及看，而C题虽然最后看了，但是时间来不及写了。

A题：A - Painter HDU - 5319

思路：因为 R 画的方向和B画的方向是不同的，所以分开遍历两次就可以。没仔细阅读题目导致我认为R和B画的方向不确定，因此我以为是一道很复杂的DFS，后面听题解，听到 R的方向和B的方向是规定的时候，人都傻了

坑点还是有的：1.方阵不是n*n的我只知道行数，而列数需要通过计算（样例害人）

　　　　　　　2.画线的时候长度是不确定的，就是说可以画到一半停下了，不一定会到达边界

 1 nclude<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int inf = 0x3f3f3f3f;
 5 const int maxn = 500030;
 6 int n;
 7 char str[100][100];
 8 int ans = 0;
 9 int len;
10 int T;
11 void solve1(int i,int j){
12     for(int k = i,l = j ; k < n && l < len ; k++, l++){
13         if(str[k][l]=='G'){
14             str[k][l] = 'B';
15         }else if(str[k][l] =='R'){
16             str[k][l] = '.';
17         }else{
18             break;
19         }
20     }
21 }
22 void solve2(int i,int j){
23     for(int k = i ,l = j; k < n  && l >= 0 ; l-- ,k++){
24         if(str[k][l]=='G'){
25             str[k][l]= 'R';
26         }else if(str[k][l]=='B'){
27             str[k][l] = '.';
28         }else{
29             break;
30         }
31     }
32 }
33 void init(){
34     for(int i = 0 ; i < n ; i++){
35         puts(str[i]); 
36     } 
37     puts("分割线");
38 }
39 
40 int main(){
41     scanf("%d",&T);
42     while(T--){
43         ans = 0;
44         memset(str,0,sizeof(str));
45         scanf("%d",&n);getchar();
46         for(int i = 0 ; i < n ; i++){
47             gets(str[i]);
48         }
49         len = strlen(str[0]);
50         for(int  i = 0 ; i < n ; i++){
51             for(int j = 0 ; j < len ; j++){
52                 if(str[i][j]=='R' || str[i][j] == 'G'){
53                     solve1(i,j);
54                     ans++;
55                     //init();
56                 }
57                 if(str[i][j] == 'B'){
58                     solve2(i,j);
59                     ans++;
60                     //init();
61                 }
62             }
63         }
64         printf("%d
",ans);    
65     } 
66     return 0;
67 }
68 
69 /*
70 2
71 4
72 RR.B
73 .BG.
74 .BRR
75 B..R
76 4
77 RRBB
78 RGGB
79 BGGR
80 BBRR
81 */

B题：B - Misaki's Kiss again HDU - 5175

思路： M^N=GCD(M,N) 通过转化可以得到，M = N^GCD(M,N);,我们本来就是已知N来求M，那这样的话们就可以直接遍历N的因子，计算M，并且M需要满足等式即可

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int inf = 0x3f3f3f3f;
 5 const int maxn = 2000030;
 6 ll n;
 7 vector<ll>vec;
 8 ll gcd(ll a,ll b){
 9     if(b == 0) return a;
10     else return gcd(b,a%b);
11 }
12 ll cnt = 1;
13 ll ans;
14 ll pos = 0;
15 ll num[maxn];
16 int main(){
17     while(~scanf("%lld",&n)){
18         memset(num,0,sizeof(num));
19         pos = 0;
20         for(ll i = 1; i*i <= n ; i++){
21             if(n % i == 0){
22                 ll m = i ^ n;
23                 if(gcd(n,m) == i && m != 0 && m <= n) num[pos++] = m;
24                 m = (n/i)^n;
25                 if(gcd(n,m) == (n/i) && m != 0&& m <= n) num[pos++] = m;    
26             }
27         }
28         sort(num,num+pos);
29         printf("Case #%lld:
",cnt++);
30         printf("%lld
",pos);
31         for(ll i = 0 ; i < pos ; i++){
32             printf("%lld",num[i]);
33             if(i != pos - 1) printf(" ");
34         }
35         printf("
");
36     }
37     return 0;
38 }

C题：C - Discounts CodeForces - 161B

思路：因为要打折最多，那么打折的越贵越好，贪心打折的价格和打折的数量就好了

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int maxn = 500030;
struct node{
    ll num;
    ll val;
}pen[maxn],tot[maxn];
vector<node>vec[5000];
ll n,k,ci,ti;
int cmp(struct node & a,struct node & b){
    return a.val > b.val;
}
double sum  =0;
ll cnt1,cnt2;
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>k;
    for(int i = 1; i <= n ; i++){
        cin>>ci>>ti;
        sum += ci;
        if(ti == 1){
            tot[cnt1].val = ci;
            tot[cnt1].num = i;
            cnt1++;
        }else{
            pen[cnt2].val = ci;
            pen[cnt2].num = i;
            cnt2++; 
        }
    }
    sort(tot,tot + cnt1,cmp);
    sort(pen,pen + cnt2,cmp);
    int cnt = 1;
    for(int i = 0; i < cnt1 ; i++){
        vec[cnt].push_back(tot[i]);
        if(cnt != k) cnt++;
    }
    if(cnt1 < k){
        for(int i = 0; i < cnt1;  i++){
            sum -= tot[i].val/2.0;
        }
        int ss = 0;
        for(int i = cnt1 + 1 ; i < k ; i++){
            vec[i].push_back(pen[ss]);
            ss++;
        }
        for(int i = ss ; i < cnt2 ; i++){
            vec[k].push_back(pen[i]);
        }
    }else{
        for(int i = 0 ; i < k - 1 ; i++){
            sum -= tot[i].val/2.0;
        }
        if(cnt1 != 0 && cnt2 != 0) sum -= min(tot[cnt1 - 1].val,pen[cnt2 - 1].val)/2.0;
        if(cnt2 == 0) sum -= tot[cnt1-1].val/2.0; 
        for(int i = 0 ;  i < cnt2 ; i++){
            vec[k].push_back(pen[i]);
        }
    }
    printf("%.1lf
",sum);
    for(int i = 1 ; i <= k ; i++){
        printf("%d",vec[i].size());
        for(int j = 0 ; j < vec[i].size() ; j++){
            printf(" %lld",vec[i][j].num);
        }
        printf("
");
    }
    return 0;
}

D题：D - Remainders Game CodeForces - 687B

思路：可以知道很多 x % ci，根据这些条件要求 x%k，可以推理结论，只要所有ci的最小公倍数是k的倍数就好了。

　　　c = n*k，x % c = x % n * x % k = x % c1 * x %c2.....（所有质因子）。以为数据会爆ll ，所以再求lcm的时候要边求边取模。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int maxn = 500030;
ll n,k,c;
ll ans = 1;
ll gcd(ll a ,ll b){
    return b == 0 ? a : gcd(b,a%b);
}
ll lcm(ll a,ll b,ll ret){
    return ((a%ret)*(b%ret)/gcd(a,b))%ret;
}

int main(){
    ios::sync_with_stdio(false);
    cin>>n>>k;
    for(int i = 1; i <= n ; i++){
        cin>>c;
        ans = lcm(c,ans,k)%k;
    }
    if(ans % k == 0) printf("Yes
");
    else cout<<"No"<<endl;
    return 0;
}

E题：E - Present CodeForces - 460C

思路：二分答案进行查找，然后用差分 + 前缀和的方法维护操作次数，得出答案。

这道题是今天最大的收获了，学到了差分的方法，用于维护区间值的改变，高兴！！！

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int maxn = 500030;
const int eps =1e-6;
ll a[maxn];
ll n,m,w;
ll sum[maxn];
ll op;
bool check(ll cur){
    op = 0;
    memset(sum,0,sizeof(sum));
    for(int i = 1; i <= n ; i++){
        sum[i] += sum[i - 1];
        if(sum[i] + a[i] < cur){
            op += cur - sum[i] - a[i];
            sum[i + w] -= cur - a[i] - sum[i];
            sum[i] += cur - a[i] - sum[i];
        }
    }
    if(op<= m) return true;
    else return false;
}

int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m>>w;
    for(int i = 1; i <= n ; i++){
        cin>>a[i];
    }
    ll l = 1,r = 1e12;
    while(r - l > 1){
        ll mid = (l + r +1)/2;
        if(check(mid)){
            l = mid; 
        }else{
            r = mid;
        }
    }
    cout<<l<<endl;
    return 0;
}

F题：F - Hill Climbing CodeForces - 406D

好难还不会，之后加油补。

一个从很久以前就开始做的梦。