反思

打比赛前请调整好状态，赛时请思考问题而非一直想着暴力无脑做法。

B - 填充方块

分析

思维题，这类题先满足条件苛刻的。什么/2，%，n-要敏感

代码

//思维——思考，先满足苛刻要求的
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
int a,b,n;
void solve()
{
    cin>>a>>b>>n;
    b/=2;
    //n%3==0 n-3*b
    //剩下的a补齐
    n=max(n%3,n-3*b);
    //1*2的横着放
    if(a>=n)puts("YES");
    else puts("NO");//细心！！！puts不要和cout endl混用
}
signed main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int t;
    cin>>t;
    while(t--)solve();

    return 0;
}

C - map使用

分析

不要无脑暴力！！！给出两种做法，显然是考虑哪个更优（贪心），这类题明显是讨论数的性质来做。
对两种做法分析：
·ai+aj<=0:显然负数相加符合条件，这个优先考虑。其次是正数与负数相加，零之间相加
·ai^aj<=0:如果在比赛中遇到自己不熟悉的知识点，那就用编译器去探索性质，（代码在下面），正数^正数和负数^负数均正，相同数^为0，正数^负数为负
据上，负数单独统计用于自身配对和与正数异或，正数中先把相同数处理掉，因此需要使用map统计次数
所以以后遇到这类题，先演算一下性质，讨论一下情况。

代码

#include<bits/stdc++.h>
using namespace std;
int a=-1,b=-100,f=-100,c=1,d=1,e=100;
int main()
{
    cout<<(a^b)<<endl;
    cout<<(a^c)<<endl;
    cout<<(c^d)<<endl;
    cout<<(c^e)<<endl;
    cout<<(b^f)<<endl;
    return 0;
}
/*99
-2
0
101*/

#include<bits/stdc++.h>
#define x first
#define y second
#define int long long
#define endl '\n'
using namespace std;
int n,k,c1,c2;
map<int,int>mp;
void solve()
{
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>k;
        if(k<0)c1++;
        else mp[k]++;
    }
    for(auto &w:mp)
    {
        n-=(w.y/2)*2;// /2是配对，*2是消去两个数字
        w.y%=2;
        c2+=w.y;//剩下的正数
    }
    if(c1>c2)
    n-=(c2*2+(c1-c2)/2*2);
    else
    n-=c1*2;
    cout<<n<<endl;
}
signed main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int t=1;
    //cin>>t;
    while(t--)solve();

    return 0;
}

D - 最大字典序

分析

之前做过类似的题目，不过那道题是字符串之间的拼接去找最大字典序，这道题字符串内部顺序不变但不需要连续，涉及排序贪心，那用大根堆就行。还是那句话，把样例分析了，就知道怎么做了。

样例

2
92 86

输出是9862，无非一开始先取字典序最大的串，因为要保持内部顺序所以在使用时也只能顺序使用这个字符串，取了92中的9，然后库里还有2和86，86字典序更大，取8，剩下2和6，取6，最后取2。

之前的题

#include<bits/stdc++.h>
using namespace std;
int n;
bool cmp(string a,string b)
{
    return a+b<b+a;
}
int main()
{
    cin>>n;
    string s[n];
    for(int i=0;i<n;i++)cin>>s[i];
    sort(s,s+n,cmp);
    for(int i=0;i<n;i++)cout<<s[i];
    return 0;
}

本题代码

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=1e5+10;
int n;
string s[N],ans;
void solve()
{
    cin>>n;
    priority_queue<string>q;
    for(int i=0;i<n;i++)
    {
        cin>>s[i];
        q.push(s[i]);
    }
    //段错误一般是数据结构使用不当
    while(q.size())
    {
        auto t=q.top();
        q.pop();
        ans+=t[0];
        if(t.size()>1)//没有这个判断，字符串截取会出错
        q.push(t.substr(1));
    }
    cout<<ans;
}
signed main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int t=1;
    //cin>>t;
    while(t--)solve();

    return 0;
}

E - 构造连通块

分析

这次比赛暴露出的点：思维题不思考，公式题靠暴力，算法题想不出算法
这题连边构造连通图，连通图-dfs、bfs、并查集都可以。这题基本全是板子，连边就是合并，合并计算代价，就是因为这个连通块就这两个点，所以求个最值。最终把所有连通块求个和，如何找连通块？看祖先。最后剩下两个连通块，再去合并为连通图，这里的代价是较大的那个连通块的，所以较小的没加上，用总和减去那个较小的，为何这里求最小的？因为最小的才是最不可能用上的代价。

i==find(i)

代码

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=1e5+10;
int n,m,a[N],p[N];
int find(int x)
{
    if(x!=p[x])p[x]=find(p[x]);
    return p[x];
}
signed main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        p[i]=i;
    }
    while(m--)
    {
        int x,y;
        cin>>x>>y;
        x=find(x),y=find(y);
        p[y]=x;
        a[x]=max(a[x],a[y]);
    }
    int ans=0,mx=1e9;
    for(int i=1;i<=n;i++)
    if(i==find(i))
    {
        ans+=a[i];
        mx=min(mx,a[i]);
    }
    cout<<ans-mx;
    return 0;
}

F题组合数学……暂时不是很想掌握