2020秦皇岛(F，E) 思维训练

F. Friendly Group

题意：给定一个无向图，每个连通分量的贡献是：边数-节点数，请你求出整个图选择那些点和边，能够使得贡献最大。

思路：dsu统计连通分量，然后对于每条边划分如相应的连通分量即可。

PS：vp的时候把求和下意识搞成最大值了，疯狂wa2

#include 
using namespace std;
#define endl '\n'
#define int long long
const int N = 3e6+100;

int dsu[N];
int ans[N];
int siz[N],sp,vis[N];
int tfind(int x)
{
    if(x==dsu[x])
        return x;
    return dsu[x]=tfind(dsu[x]);
}
void tmerge(int x,int y)
{
    x=tfind(x);y=tfind(y);
    if(x==y)
        return;
    dsu[y]=x;
    siz[x]+=siz[y];
}
pair<int,int> pa[N];

signed main()
{
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    int t;
    int cnt=0;
    for(cin>>t;t;t--)
    {
        cnt++;
        int n,m;
        cin>>n>>m;
        for(int i=1;i<=n+100;i++)
        {
            dsu[i]=i;siz[i]=1;ans[i]=0,vis[i]=0;
        }
        for(int i=1;i<=m;i++)
        {
            int a,b;
            cin>>a>>b;
            pa[i].first=a;pa[i].second=b;
            tmerge(a,b);
        }
        for(int i=1;i<=m;i++)
        {
            int x=tfind(pa[i].first);
            ans[x]++;
        }
        int maxx=0;
        for(int i=1;i<=n;i++)
        {
            if(i==tfind(i))
                if(ans[i]-siz[i]>0)
                    maxx+=ans[i]-siz[i];
        }
        cout<<"Case #"<<cnt<<": "<<maxx;
        if(t!=1)
            cout<<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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

E. Exam Results
题意：对于一门考试，及格线是最高分x乘以p%，给定n个学生在心态好与差的情况下的分数ai与bi，给定常数p，请你估算出，在最理想情况下有多少人及格。

思路：不断枚举最大值，这个过程中及格线也在不断变化，每次把淘汰的最大值先从及格区减去，换成他们发挥不好的情况，然后再去判断能否达到新的及格线。

代码偷了队友的，思路虽然有但是代码我真写不出来。

#include 
using namespace std;
#define endl '\n'
#define int long long
const int N = 3e6+100;
int t,n,p;
struct node
{
    int id,a,b;
    bool operator<(const node &c)const
    {
        return c.a>a;
    }
}stu[N];
map<int,int>mp;
vector<int>g[N],v;
set<int>s;
signed main()
{
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    cin>>t;
    int ca=0;
    while(t--)
    {
        cin>>n>>p;mp.clear();s.clear();v.clear();
        for(int i=1;i<=n;i++) g[i].clear();
        int cnt=0,maxx=0,ct=0;
        for(int i=1;i<=n;i++)
        {
            cin>>stu[i].a>>stu[i].b,stu[i].id=i;
            if(!mp[stu[i].a]) mp[stu[i].a]=++cnt;
            g[mp[stu[i].a]].push_back(i);
            maxx=max(maxx,stu[i].b);
        }
        priority_queue<node>q;
        for(int i=1;i<=n;i++)
        {
            if(stu[i].a>=maxx) s.insert(stu[i].a);
        }
        s.insert(maxx);
        for(auto x:s) v.push_back(x);
        double jg=v.back()*p*1.0/100;
        int ans=0,res=0;
        for(int i=1;i<=n;i++)
        {
            double grade=stu[i].a;
            //cout<<"grade="<if(grade>=jg) res++;
            else q.push(stu[i]);
        }
        ans=max(ans,res);
        //cout<<"ans="<
        int las=v.back();v.pop_back();
        while(v.size()>0)
        {
            double now=v.back()*p*1.0/100;
            for(auto x:g[mp[las]])
            {
                double grade=stu[x].b;
                if(grade<now)
                {
                    res--;
                    stu[x].a=stu[x].b;
                    q.push(stu[x]);
                }
            }
            while(!q.empty())
            {
                double grade=q.top().a;
                if(grade>=now) res++,q.pop();
                else break;
            }
            ans=max(res,ans);las=v.back();
            //cout<<"res="<
            v.pop_back();
        }
        cout<<"Case #"<<++ca<<": "<<ans;
        if(t) cout<<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
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

C. LIS or Reverse LIS?
我一开始读错题了，待会儿说我复习的nlogn求lis

题意：给定一个数列a，你现在可以对其进行任意排列，求出能够获得的a的LIS与A的LIS的最大值

思路：显然这应该构造一个类似于小山一样的东西，对于多次出现的数，他的贡献有且只有1，对于仅仅出现一次的数，假设有cnt个，贡献是cnt/2（向上取整）

# include
using namespace std;
# define mod 1000000009
 
typedef long long int ll;
map<int,int>mp;
int main ()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        mp.clear();
        int cnt=0;
        for(int i=1;i<=n;i++)
        {
            int x;
            cin>>x;
            mp[x]++;
 
            if(mp[x]<=2)
                cnt++;
        }
 
        int ans=cnt/2;
        if(cnt%2)
            ans++;
        cout<<ans<<'\n';
 
    }
 
 
    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

nlogn级别求LIS如下（不是正解！！！）
这是我看到LIS和1e5数据直接反射的一个东西，顺带重构一下当时的代码。

#include 
using namespace std;
//#define int long long
#define endl '\n'
const int N = 2e5+100;
int a[N],a1[N],b[N];

int getLIS(int a[],int n)
{
    b[1]=a[1];
    int len=1;
    for(int i=2;i<=n;i++)
    {
        if(b[len]<a[i])//<与lower结合，代表严格递增子序列
        {
           b[++len]=a[i];
        }
        else
        {
            int pos=lower_bound(b+1,b+len+1,a[i])-b;
            b[pos]=a[i];
        }
    }
    return len;
}
int getLDS(int a[],int n)
{
    b[1]=a[1];
    int len=1;
    for(int i=2;i<=n;i++)
    {
        if(b[len]>=a[i])//>=与upper结合，代表非严格递减子序列
        {
           b[++len]=a[i];
        }
        else
        {
            int pos=upper_bound(b+1,b+len+1,a[i],greater<int>())-b;
            b[pos]=a[i];
        }
    }
    return len;
}
signed main()
{
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    int t;
    for(cin>>t;t;t--)
    {
        int n;
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            a1[n-i+1]=a[i];
        }
        int ans1=getLIS(a,n);
        int ans2=getLIS(a1,n);
        cout<<min(ans1,ans2)<<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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

B. AND Sorting

题意:给定一个排列，对于满足a[i]&a[j]=X的(i,j)可以交换，请你判断，如果想把给定的排列变成正序，那么最大的X值是多少。

思路：没猜出来结论，证明也不太会，看了题解了。属于是C能秒B不会，怪哉怪哉

&操作做的越多，交换的越多，X的值就越小，所以最优的方案就是直接和对应的位置来个交换，所以只要把所有a[i]!=i的位置做一次且运算即可得到最大的X

#include 

using namespace std;
#define endl '\n'
const int N = 2e6+100;
int a[N];
char s[N];
int main()
{
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    int t;
    for(cin>>t;t;t--)
    {
        int n;
        cin>>n;
        int res=(1<<20)-1;
        for(int i=0;i<n;i++)
        {
            cin>>a[i];
            if(a[i]!=i)
                res&=i;
        }
        cout<<res<<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

C. Sum of Substrings(屎山代码警告)

题意：给定个01串串，对于每个位置i，i和i+1位置构成的允许含有签到0的十进制数的和，就是这个串的值。现在你可以进行x次操作，每次可以交换相邻的两个字符，请问经历了x次操作后你能得到的值最小的字符串的值是多少。

思路：除了两边的1，其他的1贡献稳定是11，判定一下能不能把一个1弄两边就行了。

#include 
using namespace std;
#define endl '\n'
#define int long long
const int N = 3e6+100;
int a[N];
int ans[N];
signed main()
{
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    int t;
    for(cin>>t;t;t--)
    {
        int n,k;
        cin>>n>>k;
        bool falg=false;
        for(int i=1;i<=n;i++)
        {
            char ch;
            cin>>ch;
            a[i]=ch-'0';
            if(a[i])
                falg=true;
        }
        if(!falg)
        {
            cout<<0<<endl;
            continue;
        }
        int fi,la;
        for(int i=1;i<=n;i++)
        {
            if(a[i])
            {
                fi=i;
                break;
            }
        }
        for(int i=n;i>=1;i--)
        {
            if(a[i])
            {
                la=i;
                break;
            }
        }
        //cout<
        if(fi==la)
        {
            if(n-la<=k)
            {
                swap(a[n],a[la]);
            }
            else if(la-1<=k)
            {
                swap(a[fi],a[1]);
            }
        }
        else
        {
            if(n-la<=k)
            {
                swap(a[n],a[la]);
                k-=(n-la);
            }
            if(fi-1<=k)
            {
                swap(a[fi],a[1]);
            }
        }
        int ans=0;
        for(int i=1;i<=n;i++)
        {
            //cout<
            if(a[i])
            {
                if(i==1)
                {
                    ans+=10;
                }
                else if(i==n)
                {
                    ans+=1;
                }
                else
                {
                    ans+=11;
                }
            }
        }
        //cout<
        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
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