写完这个就去搞有趣的实训了！

img

Codeforces Round 938 (Div. 3)

A

能买一个自然全部都买一个

如果可以买两个那就需要考虑取余

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define frep(i,a,n) for(int i=a;i>=n;i--)
#define int long long
const int N=1e5+100;
#define PII pair<int,int>
#define lowbit(x) (x&(-x))
const int mod=1e9+7;
const double pai=acos(-1.0);
#define ios ios::sync_with_stdio(0); cin.tie(0),cout.tie(0);
#define LF(x)   fixed<<setprecision(x)
int a[N];
#define CY cout<<"YES"<<'\n'
#define CN cout<<"NO"<<'\n'
void Totoro()
{
int n,x,y;
cin>>n>>x>>y;
if(x*2<=y)
{
    cout<<n*x<<'\n';
}
else
{
    cout<<n/2*y+(n%2)*x<<'\n';
}

}
signed main()
{  
ios;
int t;
cin>>t;
while(t--)
{
    Totoro();
}
return 0;
}

B

B题实际上我们只需要两层循环弄个map,如果这个没有出现过，就出问题了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define frep(i,a,n) for(int i=a;i>=n;i--)
//#define int long long
const int N=1e6+100;
#define PII pair<int,int>
#define lowbit(x) (x&(-x))
const int mod=1e9+7;
const double pai=acos(-1.0);
#define ios ios::sync_with_stdio(0); cin.tie(0),cout.tie(0);
#define LF(x)   fixed<<setprecision(x)
int a[N];
void Totoro()
{
map<ll,int>mp;
//9x+9c+9d
//4x+2c+2d
int n,c,d;
cin>>n>>c>>d;
rep(i,1,n*n)
{
    cin>>a[i];
    mp[a[i]]++;
}
sort(a+1,a+1+n*n);
int x=a[1];
for(int i=0;i<=n-1;i++)
{
for(int j=0;j<=n-1;j++)
{
if(!mp[x+i*c+j*d])
{
   cout<<"NO"<<'\n';
    return;
}    
mp[x+i*c+j*d]--;
}
}
cout<<"YES"<<'\n';
}
signed main()
{  
ios;
int t;
cin>>t;
while(t--)
{
    Totoro();
}
return 0;
}

C

C题如果我们一开始就判断能不能全部弄完，然后再两边找二分之一，那么只需要特判最后一个中间相遇能不能搞定就可以了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define frep(i,a,n) for(int i=a;i>=n;i--)
#define int long long
const int N=1e6+100;
#define PII pair<int,int>
#define lowbit(x) (x&(-x))
const int mod=1e9+7;
const double pai=acos(-1.0);
#define ios ios::sync_with_stdio(0); cin.tie(0),cout.tie(0);
#define LF(x)   fixed<<setprecision(x)
int a[N];
void Totoro()
{
int n;
cin>>n;
int m;
cin>>m;
int sum=0;
rep(i,1,n)
{
    cin>>a[i];
    sum+=a[i];
}
if(m>=sum)
{
    cout<<n<<'\n';
    return;
}
int suml=0;
int sumr=0;
int x=(m+1)/2;
int cnt_i=0;
rep(i,1,n)
{
suml+=a[i];
if(suml<=x)
{
    cnt_i=i;
}
}
int cnt_j=n+1;
frep(j,n,1)
{
sumr+=a[j];
if(sumr<=m/2)
{
    cnt_j=j;
}
}
if(cnt_j-1==cnt_i+1)
{
if(m-sumr-suml==a[cnt_j-1])
{
    cout<<n<<'\n';
    return ;
}
else
{
cout<<n-cnt_j+1+cnt_i<<'\n';
return ;
}
}
cout<<n-cnt_j+cnt_i+1<<'\n';
}
signed main()
{  
ios;
int t;
cin>>t;
while(t--)
{
    Totoro();
}
return 0;
}

D

还是用map记录，然后只需要把0变成-1然后去讨论即可，思路很直接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define frep(i,a,n) for(int i=a;i>=n;i--)
#define int long long
const int N=1e6+100;
#define PII pair<int,int>
#define lowbit(x) (x&(-x))
const int mod=1e9+7;
const double pai=acos(-1.0);
#define ios ios::sync_with_stdio(0); cin.tie(0),cout.tie(0);
#define LF(x)   fixed<<setprecision(x)
int a[N];
int b[N];
void Totoro()
{
int n,m,k;
cin>>n>>m>>k;
rep(i,1,n)
{
    cin>>a[i];
}
int ans=0;
map<int,int>mp;
rep(j,1,m)
{
cin>>b[j];   
mp[b[j]]++;
}
int sum=0;
rep(i,1,m)
{
if(mp[a[i]]>0)
{
mp[a[i]]--;
sum++;
if(mp[a[i]]==0)
{
    mp[a[i]]=-1;
}
}
else if(mp[a[i]]<0)
{
    mp[a[i]]--;
}
}
if(sum>=k)
{
    ans+=1;
}
rep(i,1,n-m)
{
if(mp[a[i]]<0)
{
if(mp[a[i]]==-1)
{
    sum--;
    mp[a[i]]=1;
}
else 
{
    mp[a[i]]++;
}
}
else if(mp[a[i]]>0)
{
    mp[a[i]]++;
    sum--;
}

if(mp[a[i+m]]<0)
{
   mp[a[i+m]]--;     
}
else if(mp[a[i+m]]==1)
{
    mp[a[i+m]]=-1;
    sum++;
}
else if(mp[a[i+m]]>0)
{
    mp[a[i+m]]--;
    sum++;
}
if(sum>=k)
{
    ans++;
}
}
cout<<ans<<'\n';
}
signed main()
{  
ios;
int t;
cin>>t;
while(t--)
{
    Totoro();
}
return 0;
}

E

取模异或看看和第一个相等吗

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define frep(i,a,n) for(int i=a;i>=n;i--)
#define int long long
const int N=1e5+100;
#define PII pair<int,int>
#define lowbit(x) (x&(-x))
const int mod=1e9+7;
const double pai=acos(-1.0);
#define ios ios::sync_with_stdio(0); cin.tie(0),cout.tie(0);
#define LF(x)   fixed<<setprecision(x)
void Totoro()
{
    int n;
    cin >> n;
    string s;
    cin >> s;
    for (int k = n; ; k--) 
    {
        std::vector<int> a(k);
        for (int i = 0; i < n; i++) 
        {
            a[i % k] ^= '1' - s[i];
        }
        if (a == vector(k, a[0])) 
        {
           cout << k << "\n";
            return;
        }
    }
}
signed main()
{
    int t;
    cin>>t;
    while(t--)
    {
        Totoro();
    }
    return 0;
}

F

知道1，2，3异或是0即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define frep(i,a,n) for(int i=a;i>=n;i--)
#define int long long
const int N=1e5+100;
#define PII pair<int,int>
#define lowbit(x) (x&(-x))
const int mod=1e9+7;
const double pai=acos(-1.0);
#define ios ios::sync_with_stdio(0); cin.tie(0),cout.tie(0);
#define LF(x)   fixed<<setprecision(x)
int a;
void Totoro()
{
int b,c,d;
cin>>a>>b>>c>>d;
cout<<a/2+b/2+c/2+d/2+(a%2&&b%2&&c%2)<<'\n';
}
signed main()
{  
ios;
int t;
cin>>t;
while(t--)
{
    Totoro();
}
return 0;
}

G

参考队友huangyu的写法的

只需要枚举一下a[1][1]的因子即可，然后看看路线上的因子有没有这个，最后类似dp去递推即可

这个做法稳过的，不过是1014ms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define frep(i,a,n) for(int i=a;i>=n;i--)
#define int long long
const int N=1e5+100;
#define PII pair<int,int>
#define lowbit(x) (x&(-x))
const int mod=1e9+7;
const double pai=acos(-1.0);
#define ios ios::sync_with_stdio(0); cin.tie(0),cout.tie(0);
#define LF(x)   fixed<<setprecision(x)
int b[110][110];
int a[110][110];
int n,m;
int v[N];
int gcd(int x,int y)
{
    if(!y)
    {
        return x;
    }
    return gcd(y,x%y);
}
bool check(int x)
{
    rep(i,1,n)
    {
        rep(j,1,m)
        {
            if(a[i][j]%x==0)
            {
                b[i][j]=1;
            }
            else
            {
                b[i][j]=0;
            }
        }
    }
b[0][1]=1;
//保证一开始b[1][1]=1    
rep(i,1,n)
{
    rep(j,1,m)
    {
        if(b[i][j]&&(b[i-1][j]||b[i][j-1]))
        {
            b[i][j]=1;
        }
        else
        {
            b[i][j]=0;
        }
    }
}    
if(b[n][m])
{
    return 1;
}
return 0;
}
void Totoro()
{
int cnt=0;    
cin>>n>>m;
rep(i,1,n)
{
    rep(j,1,m)
    {
        cin>>a[i][j];
    }
}
int y=gcd(a[1][1],a[n][m]);
rep(i,1,y/i)
{
if(y%i==0)
{
    v[++cnt]=i;
    v[++cnt]=y/i;
}
}
sort(v+1,v+1+cnt);
frep(i,cnt,1)
{
    if(check(v[i]))
    {
        cout<<v[i]<<'\n';
        return ;
    }
}


}
signed main()
{
    int t;
    cin>>t;
    while(t--)
    {
        Totoro();
    }
    return (0-0);
}

有一种TLE做法，但也没想到，就是用set去做

每次插这个位置能变成的数字，会多个log

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define frep(i,a,n) for(int i=a;i>=n;i--)
#define int long long
const int N=1e5+100;
#define PII pair<int,int>
#define lowbit(x) (x&(-x))
const int mod=1e9+7;
const double pai=acos(-1.0);
#define ios ios::sync_with_stdio(0); cin.tie(0),cout.tie(0);
#define LF(x)   fixed<<setprecision(x)
int b[110][110];
int gcd(int x,int y)
{
    if(!y)
    {
        return x;
    }
    return gcd(y,x%y);
}
set<int>a[110][100];
void Totoro()
{
    int n,m;
    cin>>n>>m;
    rep(i,1,n)
    {
        rep(j,1,m)
        {
            cin>>b[i][j];
            a[i][j].clear();
        }
    }
    a[1][1].insert(b[1][1]);
rep(i,1,n)
{
rep(j,1,m)
{
    for(auto k:a[i][j])
    {
if(i!=n)
{
    a[i+1][j].insert(gcd(k,b[i+1][j]));
}
if(j!=m)
{
    a[i][j+1].insert(gcd(k,b[i][j+1]));
}
    }
}
}
cout<<*(--a[n][m].end())<<'\n';
}
signed main()
{
    int t;
    cin>>t;
    while(t--)
    {
        Totoro();
    }
    return 0;
}