Chaos Begin

题目大意

二维平面上有两组点，每组有n个点，其中

但现在不知道点属于a,b哪个集合，需要你找出所有可能的

解题思路

先对所有2n个点排序，那么一定包含于最小的两个点开始与所有点做差的所有情况中。

由于点对完全随机，所以可以直接这样遍历上面所有情况找到符合的作为答案。时间复杂度会被降到nlogn（因为有不符合直接剪纸处理）

假设为可能的答案，我们只需要先把所有点存入map计数，然后从小到大扫一遍，如果这个点的数量大于等于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
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 i64 = long long;
#define endl '\n'

bool multi=1;

void solve(){
    int n;
    cin >> n;
    n *= 2;
    vector<pair<int, int>> p(n);
    for(int i = 0; i < n; i++){
        cin >> p[i].first >> p[i].second;
    }
    sort(p.begin(), p.end());
    map<pair<int, int>, int> f;
    vector<pair<int, int>> ans;
    for(auto v:p) f[v]++;
    for(int i = 1; i < n; i++){
        int dx = p[i].first - p[0].first, dy = p[i].second - p[0].second;
        vector<pair<int, int>> tmp;
        bool flag = 0;
        for(int j = 0; j < n; j++){
            if(f[p[j]]){
                if(f[{p[j].first + dx, p[j].second + dy}]){
                    f[{p[j].first + dx, p[j].second + dy}]--;
                    f[p[j]]--;
                    tmp.push_back({p[j].first + dx, p[j].second + dy});
                    tmp.push_back(p[j]);
                }else{
                    flag = 1;
                    break;
                }
            }
        }
        if(!flag){
            ans.push_back({dx, dy});
            ans.push_back({-dx,-dy});
        }
        for(auto it:tmp) f[it]++;
    }
    sort(ans.begin(), ans.end());
    ans.erase(unique(ans.begin(), ans.end()), ans.end());
    cout << ans.size() << '\n';
    for(auto it:ans){
        cout << it.first << ' ' << it.second << '\n';
    }
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int T=1;
    if(multi) cin>>T;
    while(T--){
        solve();
    }

    return 0;
}

Out of Control

题目大意

给定n个时间戳，最初栈为空，当接受一个时间戳信号会附加在堆栈末尾，若这个时间戳比之前的末尾小，那么这个时间戳会变成上一个时间戳。但由于网失控，使得可能会以任意顺序接收请求且可能错过某些请求，现在问你堆栈数量分别为1~n时的可能情况的数量。

解题思路

先进行离散化处理记录每个数的数量和前缀数量。

下面的j结尾都指的是离散化后的值。

定义为堆栈数量为i的情况中，以1~j为堆栈结尾的方案数。

那么它一定能从转移过来，因为j从1遍历到tot（离散化后的总数），那么1~j-1结尾的堆栈数量为i-1的数列后末尾都可以加上j变成堆栈数量为i的以j结尾的数列。

而i-1个堆栈数量以j结尾的数加上一个小于等于j的数，判断前j个数数量是否大于等于i即能不能找到多余出来的小于等于j的数，如果能就从转移过来。

剩下的就是从转移过来。

最后的答案就是

复杂度分析

时间复杂度：O（n^2)

参考代码

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
#include<bits/stdc++.h>
using namespace std;
/*====================*/
#define endl '\n'
#define debug(a) cout<<#a<<"="<<a<<endl;
#define int long long
#define x1 x111111
#define y1 y111111
#define x0 x00000
#define y0 y00000
/*====================*/
typedef long long LL;
typedef pair<int,int> PII;
/*====================*/
const double eps=1e-8;
const int mod=1e9+7;
/*====================*/
bool multi=1;
const int N=3010;
int n,a[N];
int dp[N][N];
int b[N];
int sum[N];

void solve(){
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            dp[i][j]=0;
        }
    }
    map<int,int> mp;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        mp[a[i]]++;//离散化
    }
    int tot=0;
    for(auto it:mp){//离散化
        b[++tot]=it.second;
    }
    for(int i=1;i<=tot;i++){
        sum[i]=0;
    }
    for(int i=1;i<=tot;i++){
        sum[i]=sum[i-1]+b[i];
    }
    for(int i=1;i<=n;i++){
        dp[1][i]+=dp[1][i-1]+(i<=tot);
    }
    for(int i=2;i<=n;i++){
        for(int j=1;j<=tot;j++){
            dp[i][j]=(dp[i][j]+dp[i-1][j-1])%mod;
            if(sum[j]>=i)dp[i][j]=((dp[i][j]+dp[i-1][j]-dp[i-1][j-1])%mod+mod)%mod;
            dp[i][j]=(dp[i][j]+dp[i][j-1])%mod;
        }
    }

    for(int i=1;i<=n;i++){
        cout<<(dp[i][tot]%mod+mod)%mod<<endl;
    }
    
    
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int TTT=1;
    if(multi) cin>>TTT;
    while(TTT--){
        solve();
    }

    return 0;
}

8-bit Zoom

题目大意

给定一个图片，由n*n个字符组成，告诉你缩放比率Z，若能缩放输出缩放后的图片，若不能缩放输出error。

当100|n*Z不满足时，或缩放前无法确定某些像素的颜色，图片不能被缩放。

解题思路

dfs模拟即可。判断一下不能整除或者缩放前像素有多个颜色的清理。

当Z=100时，图片不变；当Z=125时，每个相同的颜色变成个相同的颜色；当Z=150时，每个相同的颜色变成个相同的颜色；当Z=175时，每个相同的颜色变成个相同的颜色；当Z=200时，每个相同的颜色变成个相同的颜色.

复杂度分析

时间复杂度：O(n^2)

参考代码

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
#include<bits/stdc++.h>
using namespace std;
/*====================*/
#define endl '\n'
#define debug(a) cout<<#a<<"="<<a<<endl;
#define int long long
#define x1 x111111
#define y1 y111111
#define x0 x00000
#define y0 y00000
/*====================*/
typedef long long LL;
typedef pair<int,int> PII;
/*====================*/
const double eps=1e-8;
/*====================*/
bool multi=1;
const int N=210;
char s[N][N];
char res[N][N];
bool suc;
int ed;
map<int,int> mp1={{100,1},{125,4},{150,2},{175,4},{200,1}},mp2={{100,1},{125,5},{150,3},{175,7},{200,2}};
int n,Z;


void dfs(int x1,int y1,int x2,int y2,int Z){
    if(suc==0) return;
    if(y1>n){
        ed=max(x2,y2);
        return;
    }else if(x1>n){
        dfs(1,y1+mp1[Z],1,y2+mp2[Z],Z);
        return;
    }else{
        dfs(x1+mp1[Z],y1,x2+mp2[Z],y2,Z);
    }
    for(int i=x1;i<=x1+mp1[Z]-1;i++){
        for(int j=y1;j<=y1+mp1[Z]-1;j++){
            if(s[i][j]!=s[x1][y1]){
                suc=0;
                return;
            }
        }
    }
    for(int i=x2;i<=x2+mp2[Z]-1;i++){
        for(int j=y2;j<=y2+mp2[Z]-1;j++){
            res[i][j]=s[x1][y1];
        }
    }
    
}

void solve(){
    cin>>n>>Z;
    suc=1;
    for(int i=1;i<=n;i++){
        scanf("%s",s[i]+1);
    }
    if(n*Z%100!=0){
        cout<<"error"<<endl;
        return;
    }
    dfs(1,1,1,1,Z);
    if(suc==0){
        cout<<"error"<<endl;
        return;
    }
    for(int i=1;i<=ed-1;i++){
        for(int j=1;j<=ed-1;j++){
            cout<<res[i][j];
        }
        cout<<endl;
    }

}

signed main(){
    int TTT=1;
    if(multi) cin>>TTT;
    while(TTT--){
        solve();
    }

    return 0;
}

Noblesse Code

题目大意

给定n个(a[i],b[i])，接着有q个询问，每次给你(A[i],B[i])，你可以进行任意数量操作，每次操作可以使(A[i],B[i])变成(A[i]+B[i],B[i])或(A[i],A[i]+B[i]),对于每个询问，在n个二元组a，b中，求出有多少个可以通过(A[i],B[i])变换得到。

解题思路

首先我们会发现，（A[i],B[i]）向上操作是不固定的，每层会以指数级情况增加，所以我们考虑（a[i],b[i]）向下操作，当a[i]>b[i]时，a[i]=a[i]-b[i];当a[i]<b[i]时，b[i]=b[i]-a[i]，若统计每个(a[i],b[i])所有出现的情况复杂度太高，如（1,1e18)每次只会向下减1，复杂度O(1e18)。

此时我们考虑优化，观察到例如a[i]<b[i]的情况中，(a[i],b[i])向下减，最终b[i]会变成a[i]%b[i]，令这种情况称为拐点，那么我们可以记录每个拐点的情况mp[a[i],a[i]%b[i]].push_back(a[i])；然后对于询问(A[i],B[i])，分情况二分mp即可。

例如：(2,9)->(2,7)->(2,5)->(2,3)->(2,1)->(1,1)此时(2,1)就是一个拐点，mp[{2,1}].push_back(9);

当询问出现(2,5)时二分mp[{2,5%2}]这个vector中大于5的数，为什么这样可以呢？

因为这里就取模2就体现了能到{2,1}的位置一定是从1向上递增2的顺序上去或者从2每次递增1的顺序上去。

那么mp[{2,5%2}]这个容器中大于5的数有两种情况，一种是mp[{2,1}]中(2+k,1)左边递减下来到拐点记录但这种情况不存在，因为(2+k)%1最终的数必然小于1，另一种(2,1+2k)右边递减下来到拐点被记录，这两种情况只有一种情况存在，而询问（2,5）时，我们只需二分它下来的拐点（2，1）的vector容器就可以看有多少个(2,5),(2,7),(2,9)..来计算结果。

复杂度分析

时间复杂度：

参考代码

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;
#define endl '\n'
#define debug(a) cout<<#a<<"="<<a<<endl;
#define int long long
//#define x first
//#define y second
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const double eps=1e-8;
bool multi=1;
const int N=1e5+10;

void solve(){
    int n,q;
    cin>>n>>q;
    map<PII,vector<int>> mp;

    for(int i=0;i<n;i++){
        int x,y;
        cin>>x>>y;
        while(x>0&&y>0){
            if(x>=y){
                int tx=x%y;
                mp[{tx,y}].push_back(x);
                x=tx;
            }else{
                int ty=y%x;
                mp[{x,ty}].push_back(y);
                y=ty;
            }
        }
    }

    for(auto &it:mp){
        sort(it.second.begin(),it.second.end());
    }

    auto calc=[&](int x,int y,int c){
        auto &v=mp[{x,y}];
        return (int)distance(lower_bound(v.begin(),v.end(),c),v.end());
    };

    for(int i=0;i<q;i++){
        int x,y;
        cin>>x>>y;
        int ans=0;
        if(x>y) ans=calc(x%y,y,x);
        else if(x<y) ans=calc(x,y%x,y);
        else ans=calc(0,y,y)+calc(x,0,x);
        cout<<ans<<endl;
    }
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int TTT=1;
    if(multi) cin>>TTT;
    while(TTT--){
        solve();
    }

    return 0;
}