div.4 dddd

A. To My Critics

题意

给定 33 个整数，求是否有两个加起来大于等于 1010。

解法

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;
using ull=unsigned long long;
using pii=pair<int,int>;
#define begend(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("YES")
#define NO puts("NO")
#define Yes puts("Yes")
#define No puts("No")
#define errorf(...) fprintf(stderr, __VA_ARGS__) 

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

int a[3];
void solve(int kase){
    for(int i=0;i<3;i++)a[i]=read();

    for(int i=0;i<3;i++){
        for(int j=i+1;j<3;j++){
            if(a[i]+a[j]>=10){
                YES;
                return;
            }
        }
    }    
    NO;
}

int main(){
    int T=read(),TT=1;
    while(T--){
        solve(TT++);
    }
    return 0;
}

B. Ten Words of Wisdom

题意

给定 nn 对二元组 (ai,bi)(a_i,b_i)，找出 ai≤10a_i\le 10 的二元组中，bib_i 的最大值。

解法

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
#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define begend(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("YES")
#define NO puts("NO")
#define Yes puts("Yes")
#define No puts("No")
#define errorf(...) fprintf(stderr, __VA_ARGS__) 

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

const int N = 55;
int a[N],b[N];
void solve(int kase){
    int n=read();
    for(int i=1;i<=n;i++){
        a[i]=read(),b[i]=read();
        if(a[i]>10)b[i]=-1;
    }

    int pos = max_element(b+1,b+1+n)-b;
    printf("%d\n",pos);
}


int main(){
    int T=read(),TT=1;
    while(T--){
        solve(TT++);
    }
    return 0;
}

C. Word on the Paper

题意

在一个 8×88\times 8 的字符矩阵中，有且仅有一个竖着写的单词，找出这个单词。

解法

遍历找到最上面的那个字符，然后一直往下输出即可。注意一下不要越界。

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
#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define begend(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("YES")
#define NO puts("NO")
#define Yes puts("Yes")
#define No puts("No")
#define errorf(...) fprintf(stderr, __VA_ARGS__) 

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

const int N = 10;
char mat[N][N];
void solve(int kase){
    for(int i=0;i<8;i++){
        scanf("%s",mat[i]);
    }

    for(int i=0;i<8;i++){
        for(int j=0;j<8;j++){
            if(mat[i][j]!='.'){
                while(i<8 && mat[i][j]!='.'){
                    putchar(mat[i][j]);
                    i++;
                }
                puts("");
                return;
            }
        }
    }
}

int main(){
    int T=read(),TT=1;
    while(T--){
        solve(TT++);
    }
    return 0;
}

D. Balanced Round

题意

给定 nn 个数，你可以移除任意个数，然后将它们重新排列。
求最少移除几个数，使得排列后任意两个数之间的差小于等于 kk。

解法

不妨先将原序列排序后再处理。因为最后重新排列一定是从大到小排序相邻差最小。

注意到，合法的序列一定是排序后原序列的一段连续子序列（想一想，为什么？）。因此只需要排序后找出最长的满足条件的子序列就是最多能保留的数。
移除的数就是总数减去保留的数。

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
#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define begend(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("YES")
#define NO puts("NO")
#define Yes puts("Yes")
#define No puts("No")
#define errorf(...) fprintf(stderr, __VA_ARGS__) 

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

const int N = 2e5+5;
int a[N];
void solve(int kase){
    int n=read(),k=read();
    for(int i=1;i<=n;i++){
        a[i]=read();
    }
    sort(a+1,a+1+n);

    int len = 1;
    int ans = 0;
    for(int i=2;i<=n;i++){
        if(a[i]-a[i-1]>k){
            ans = max(ans,len);
            len=1;
        }
        else len++;
    }
    ans = max(ans,len);
    printf("%d\n",n-ans);
}

int main(){
    int T=read(),TT=1;
    while(T--){
        solve(TT++);
    }
    return 0;
}

E. Cardboard for Pictures

题意

给定 nn 个数 s1,s2,…,sns_1,s_2,\ldots,s_n 以及 cc。
找到整数 ww，使得 (s1+2w)2+(s2+2w)2+…+(sn+2w)2=c(s_1+2w)^2+(s_2+2w)^2+\ldots+(s_n+2w)^2=c，保证这样的 ww 一定存在。

解法

利用一下你的初中数学知识，展开这个式子，可以得到：

4nw2+(4∑i=1nsi)w+∑i=1nsi2=c4nw^2 + \left(4\sum_{i=1}^n s_i\right) w + \sum_{i=1}^n s_i^2 = c

这是一个二次方程，可以直接用求根公式；也可以注意到左边单调增，二分找出合法的 ww（复杂度略劣）。

注意数据范围较大，使用 __int128_t 防止溢出。（可以背起来这个类型名了！）

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
#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define begend(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("YES")
#define NO puts("NO")
#define Yes puts("Yes")
#define No puts("No")
#define errorf(...) fprintf(stderr, __VA_ARGS__) 

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}
template <class T>
T read(){
    T f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

const int N = 2e5+5;
ll a[N];
void solve(int kase){
    ll n=read<ll>();
    ll c=read<ll>();
    for(int i=0;i<n;i++){
        a[i]=read<ll>();
    }


    ll factor = 0;
    for(int i=0;i<n;i++){
        factor += 4*a[i];
        c-= a[i]*a[i];
    }

    ll l=1,r=1e9;
    while(l<r){
        ll mid=(l+r)>>1;
        if((__int128_t)mid*mid*4*n+mid*factor<c)l=mid+1;
        else r=mid;
    }
    printf("%lld\n",l);
}

int main(){
    int T=read(),TT=1;
    while(T--){
        solve(TT++);
    }
    return 0;
}

F. We Were Both Children

题意

有 nn 只青蛙，每只青蛙初始都在位置 00，其跳跃距离为 aia_i。
即每只青蛙经过的位置是 0,ai,2ai,3ai,…0,a_i,2a_i,3a_i,\ldots。

现在你可以在 1∼n1\sim n 的位置中选定一个位置放置陷阱，求出一个这样的位置，使得经过陷阱的青蛙最多。

解法

考虑快速计算在位置 ii 能抓到哪些青蛙。

很简单的一个想法是对于每个青蛙都不断往它的倍数位置上的次数增加 11。这个算法的复杂度是 O(∑nai)O\left(\displaystyle \sum \dfrac{n}{a_i}\right) 的，最坏可以退化到 O(n2)O(n^2)（全是 1 的情况）

简单优化一下。对于重复出现的数字，我们记录其出现次数，然后往其倍数上加上出现次数即可。这个算法的复杂度最坏为 O(∑i=1nni)O\left(\displaystyle \sum_{i=1}^n \dfrac{n}{i}\right)，这个复杂度是调和级数，即为 O(nlog⁡n)O(n\log n)，足够通过本题。

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;
using ull=unsigned long long;
using pii=pair<int,int>;
#define begend(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("YES")
#define NO puts("NO")
#define Yes puts("Yes")
#define No puts("No")
#define errorf(...) fprintf(stderr, __VA_ARGS__) 

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

const int N = 2e5+5;
int cnt[N];
int val[N];
void solve(int kase){
    int n=read();
    for(int i=1;i<=n;i++)cnt[i]=0;

    for(int i=0;i<n;i++){
        int x=read();
        if(x>n)continue;
        cnt[x]++;
    }

    for(int i=1;i<=n;i++)val[i]=0;

    for(int i=1;i<=n;i++){
        if(!cnt[i])continue;
        for(int j=i;j<=n;j+=i){
            val[j]+=cnt[i];
        }
    }

    printf("%d\n",*max_element(val+1,val+1+n));
}

int main(){
    int T=read(),TT=1;
    while(T--){
        solve(TT++);
    }
    return 0;
}

G. The Morning Star

题意

平面上有 nn 个点。求满足两个点连线所在直线的斜率不存在，或斜率为 1,0,−11,0,-1 的点对数。（第一个点和第二个点不同，即 (A,B),(B,A)(A,B),(B,A) 计算两组）

解法

分别计算四种情况。例：如果连线的斜率不存在，那么这两个点的横坐标相同。所以这些横坐标相同的 xx 个点就有 x(x−1)x(x-1) 个合法点对。

因此，分别统计 x,y,x+y,x−yx,y,x+y,x-y 相同的点的个数即可。用一个 map 来保存，复杂度是严格 O(nlog⁡n)O(n\log n) 的。

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
#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define begend(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("YES")
#define NO puts("NO")
#define Yes puts("Yes")
#define No puts("No")
#define errorf(...) fprintf(stderr, __VA_ARGS__) 

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

void solve(int kase){
    int n=read();

    map<int,int> a,b,c,d;
    for(int i=0;i<n;i++){
        int x=read(),y=read();
        a[x]++;
        b[y]++;
        c[x+y]++;
        d[x-y]++;
    }

    ll ans = 0;
    for(auto x:a)ans += (ll)(x.second)*(x.second-1);
    for(auto x:b)ans += (ll)(x.second)*(x.second-1);
    for(auto x:c)ans += (ll)(x.second)*(x.second-1);
    for(auto x:d)ans += (ll)(x.second)*(x.second-1);
    printf("%lld\n",ans);
}


int main(){
    int T=read(),TT=1;
    while(T--){
        solve(TT++);
    }
    return 0;
}

H. The Third Letter

题意

有 nn 个变量 x1,x2,…,xnx_1,x_2,\ldots,x_n。
给出 mm 个形如 xai=xbi+dix_{a_i}=x_{b_i}+d_i 的相等关系，判断是否有解。

解法

仿照黑白染色，直接建图进行 dfs。如果这个变量取值还没有确定，直接取为 00，对于其他情况，从它的出边分别判断是否满足条件即可。

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
#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define begend(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("YES")
#define NO puts("NO")
#define Yes puts("Yes")
#define No puts("No")
#define errorf(...) fprintf(stderr, __VA_ARGS__) 

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

const int N=2e5+5;
ll pos[N];
bool vis[N];
struct Edge{
    int v,w;
};
vector<Edge> G[N];

bool ok;

void dfs(int u){
    if(vis[u])return;
    
    if(pos[u]==(ll)1e18){
        pos[u]=0;
    }
    vis[u]=1;
    
    for(auto e:G[u]){
        int v=e.v,w=e.w;
        if(pos[v]!=(ll)1e18){
            if(pos[v]!=pos[u]+e.w){
                ok=0;
            }
        }
        else{
            pos[v]=pos[u]+e.w;
            dfs(v);
        }
    }
}

void solve(int kase){
    int n=read(),m=read();
    for(int i=1;i<=n;i++){
        G[i].clear();
    }

    for(int i=0;i<m;i++){
        int u=read(),v=read(),w=read();
        G[u].push_back({v,w});
        G[v].push_back({u,-w});
    }

    for(int i=1;i<=n;i++){
        pos[i]=(ll)1e18;
        vis[i]=0;
    }

    ok=1;
    for(int i=1;i<=n;i++){
        dfs(i);
    }
    if(ok)YES;
    else NO;
}

int main(){
    int T=read(),TT=1;
    while(T--){
        solve(TT++);
    }
    return 0;
}