CF思维训练

今天的澳门VP贡献太小了，但是实在是没什么可做的，不好写。

C - Set Construction
题意：你需要构造n个集合，集合里数的值域是1到n，给定了一个n*n大小的01矩阵，对于矩阵上是1的位置代表了集合i是集合j的真子集，请你构造出n个不同的集合。

显然，这里入度最大的一个集合就是最大的集合。

1.为了保证集合的不同，我们可以对于n个集合每个集合插入一个1-n之中不同的数字作为初始化。

2.对于1，代表一个边，链接i到j，j的入度+1，根据构建的图进行拓扑排序，将拓扑序低的点代表的集合插入到父级拓扑序的集合里。

#include 

using namespace std;
const int N = 10000+100;
struct node
{
    int nex,to;
}edge[N<<1];
int head[N],tot;
int n;
int rd[N];
set<int> s[N];
void add(int from,int to)
{
    edge[++tot].to=to;
    edge[tot].nex=head[from];
    head[from]=tot;
}
void init()
{
    for(int i=1;i<=n;i++)
        s[i].clear(),rd[i]=head[i]=0;
    for(int i=1;i<=tot;i++)
        edge[i].to=edge[i].nex=0;
        tot=0;
}
void topsort()
{
    for(int i=1;i<=n;i++)
    {
        s[i].insert(i);
    }
    queue<int> q;
    for(int i=1;i<=n;i++)
    {
        if(!rd[i])
            q.push(i);
    }
    while(!q.empty())
    {
        int now=q.front();
        q.pop();
        for(int i=head[now];i;i=edge[i].nex)
        {
            int to=edge[i].to;
            rd[to]--;
            for(auto x:s[now])
                s[to].insert(x);
            if(!rd[to])
            {
                q.push(to);
            }
        }
    }
}
signed main()
{
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    int t;
    for(cin>>t;t;t--)
    {
        cin>>n;
        init();
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                char c;
                cin>>c;
                if(c=='1')
                {
                    add(i,j);
                    rd[j]++;
                }
            }
        }
        topsort();
        for(int i=1;i<=n;i++)
        {
            cout<<s[i].size()<<" ";
            for(auto x:s[i])
                cout<<x<<" ";
            cout<<'\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
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

C. Zero-Sum Prefixes
题意：一个数组，对于这个数组为0的地方可以变成任意的元素，那么请你替换合理的元素，求出这个数组的前缀和数组为0的元素的个数的最大值是多少。

思路：我们只需要对于每个a[i]为0的位置修改，那么相邻的这样的两个位置中间的这段元素就可以处理为0，我们尽可能处理这段元素中值相同的个数最多的即可。不要忘了前面的一段可以不用特殊处理就可以得到0的前缀和部分。

#include 
#define int long long
#define endl '\n'

using namespace std;
const int N=2e5+5;
int sum[N];
int a[N];
signed main()
{
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    int t;
    for(cin>>t;t;t--)
    {
        int n;
        cin>>n;
        vector<int> v;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            sum[i]=a[i]+sum[i-1];
            if(a[i]==0)
            v.push_back(i);
        }
            v.push_back(n+1);
        int ans=0;
        for(int i=1;i<v.size();i++)
        {
            map<int,int>mp;
            int maxx=0;
            for(int j=v[i-1];j<v[i];j++)
            {
                mp[sum[j]]++;
                if(mp[sum[j]]>maxx)
                    maxx=mp[sum[j]];
            }
            ans+=maxx;
        }
        for(int i=1;i<v[0];i++)
            ans+=(sum[i]==0);
        cout<<ans<<endl;
    }
    return 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

B - Elimination of a Ring

题意：给定n个数的环形数组，相邻的两数如果值相同则会自动消除，现在我们每次可以抽出其中的一个元素，抽出后元素自动补齐，请你求出最多能进行多少次抽出操作。

思路：如果整个数组不是只有两种数，那么肯定有一种方案可以使得每次抽出一个数后其他数不会自动消失，最终让所有数都落单，再慢慢抽取，所以答案应该是n。

如果只有两种数，那么必然是交替放置的，推导证明可得答案必为(n - 2) / 2 + 2

#include
#include
#include
using namespace std;
using LL = long long;
const int maxn = 105;
int a[maxn];

int main(){

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    int T;
    cin >> T;
    while(T--){
        int n;
        cin >> n;
        set<int> s;
        for(int i = 0; i < n; i++) 
            cin >> a[i], s.insert(a[i]);
        if (s.size() == 2)
            cout << (n - 2) / 2 + 2 << '\n';
        else cout << n << '\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