In The End

个人博客

0%

Codeforces 544div3题解(不完整版)

发表于 更新于 分类于 ，

修了半天博客，最后发现是域名DNS解析的问题。。。

解析里加一条TXT重新验证绑定就好了，额

接下来就是简略的题解了，不多写了，反正也没多少人看哈哈

总得来说ABCD四题都属于简单的，CD两题就考察了一些小技巧

E题的DP有点烧脑了，借鉴了大佬的一些思路推出了自己的状态转移方程

F1的图论不难，很好理解(E题比F1难多了实锤)

F2这两天更新，今天先不写了

544div3传送门：http://codeforces.com/contest/1133

A题

A题全部化成分钟运算应该是最简单的了，注意一下进位和24小时和60分钟的问题就行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include <cstdio>
using namespace std;

int main(){
    int a,b;
    int c,d;
    scanf("%d:%d",&a,&b);
    scanf("%d:%d",&c,&d);
    int t1=a*60+b;
    int t2=c*60+d;
    int s=(t2-t1)/2;
    b+=s;
    a+=b/60;
    b=b%60;
    a%=24;
    printf("%02d:%02d\n",a,b);
    return 0;
}

B题

B题就是讲礼物两两合并正好能被k整除就行，然后答案是最多的可合并的礼物数。

对于这种两两加起来被整除的问题，当时灵机一动想到的先把所有数字对k取模，这样每个礼物数都会比k小，然后问题就变成了两两加起来等于k的最大礼物数。

显然我们应该对相同数量的礼物的个数进行统计，假设k=5，我们就可以统计1和4的礼物个数，由于要合并，所以最后能用上的礼物数量一定是1和4礼物数中少的那个(剩下的就扔掉，因为已经没用了)。同样我们对2和3的也可以做相同操作。

需要注意的是如果是取模完为0的礼物应该是自己跟自己合并，也就是整除2，因为一个已经能被k整除的数字不管加上任何不被k整除的数字最后的结果一定是不被k整除，所以只能自力更生。

还有就是如果k为偶数，假设为4吧，那么我们需要对4的一半(2这个情况)这个情况也像零一样整除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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int main(){
    int n,k;
    int c[200];
    while(cin>>n>>k){
        int ans=0;
        memset(c,0,sizeof(c));
        int *a=new int[n+10];
        for(int i=0;i<n;i++){
            cin>>a[i];
            a[i]%=k;
            c[a[i]]++;
        }
        if(k%2==1) {
            for (int i = 1; i <= k / 2; i++) {
                ans+=min(c[i],c[k-i]);
            }
        }
        else{
            for (int i = 1; i < k / 2; i++) {
                ans+=min(c[i],c[k-i]);
            }
            ans+=c[k/2]/2;
        }
        ans+=c[0]/2;
        cout << ans*2 << endl;
    }
    return 0;
}

C题

题意就不赘述了，就是落在5范围内的数字越多越好，求出最大的落在5的范围内的数字数量。

首先我们对整个数组进行排，然后一遍扫描，对每个数字+5然后进行二分查找，通过

upper_bound(a,a+n,a[i]+5)-a-i)

可以算出这个数字+5范围内有多少个数字，然后扫描的时候保留最大值即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;

int main(){
    int n;
    while(cin>>n){
        ll *a=new ll[n+10];
        for(int i=0;i<n;i++)
            cin>>a[i];
        sort(a,a+n);
        int ans=0,t;
        for(int i=0;i<n;i++)
            ans=max(ans,(int)(upper_bound(a,a+n,a[i]+5)-a-i));
        cout << ans << endl;
    }
    return 0;
}

D题

D题就是考察了map的用法，我们对实数集数字进行计数即可，然后使用迭代器扫描一遍map找到数量最多的数字，将数量输出就可以了。

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
#include <iostream>
#include <cstring>
#include <map>
using namespace std;
typedef long long ll;

map<long double,int> mp;

int main() {
    ios::sync_with_stdio(false);
    int n;
    while(cin>>n) {
        int count=0;
        mp.clear();
        long double *a=new long double[n+10];
        long double *b=new long double[n+10];
        long double *t=new long double[n+10];
        for(int i=0;i<n;i++)
            cin>>a[i];
        for(int i=0;i<n;i++){
            cin >> b[i];
        }
        for(int i=0;i<n;i++) {
            if(a[i]!=0) {
                t[i] = -(b[i] / a[i]);
                if (!mp.count(t[i]))
                    mp[t[i]] = 1;
                else
                    mp[t[i]]++;
            }
            else if(a[i]==0&&b[i]==0)
                count++;
        }
        int mx=0;
        for(map<long double,int>::iterator it=mp.begin();it!=mp.end();it++)
            mx=max(mx,it->second);
        cout << mx+count << endl;
    }
    return 0;
}

E题

E题的思考难度还是很大的，我们可以借鉴一部分C题的思路用二分查找找到范围内有多少个数字，但是问题是我们统计的集合有很多重复的部分，如果使用贪心很有可能会丧失最优解。所以这道题还是得用DP来做，而且我们不应该去查找a[i]+5，应该转换思路向左找a[i]-5(因为可以方便状态转移)。

在下面的解释中我把a[i]-5算出数量的数组记为l[i]

首先还是得排序哈！然后我们开辟一个dp数组，一个维度是人数，另一个维度为组数，然后一遍扫描用a[i]-5把每个数字向左减5能包括多少数字算出来用于后面dp用。

之后我们首先把dp先全部清零，然后i从1到n开始递推，j从1到k，我们在计算dp[i][j]的时候可以从三种状态进行转移：

1.忽略这个新的数字，直接从dp[i-1][j]转移

2.这个新的数字在j-1组的时候已经算进去了，对于这种情况我们从dp[i][j-1]转移

3.这个新的数字进来可能是单独一组，也可能是跟前面的数字一组，关于到底是哪种情况我们可以使用dp[i-l[i]][j-1]找到这个新数字没来之前的状态(因为不管这个数字是不是有前面的数字跟它一组，都是j-1的，因为减去了l[i]，也就是代表我们往前回溯了一组)，然后我们的状态就从dp[i-l[i]][j-1]+l[i]转移

然后我们在这三个状态中选择最大的那个，然后随着i和j一直增加，dp[n][k]就是最后的答案了

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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
typedef long long ll;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,k;
    int dp[5005][5005];
    while(cin>>n>>k){ 
        memset(dp,0,sizeof(dp));
        int *a=new int[n+10];
        int *l=new int[n+10];
        for(int i=1;i<=n;i++)
            cin>>a[i];
        sort(a+1,a+1+n);
        for(int i=1;i<=n;i++) {
            l[i]=(int)(i-(lower_bound(a+1,a+1+n,a[i]-5)-a-1));
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=k;j++){
                dp[i][j]=max(dp[i-1][j],max(dp[i][j-1],dp[i-l[i]][j-1]+l[i]));
            }
        }
        /*for(int i=0;i<=n;i++){
            for(int j=0;j<=k;j++){
                cout << dp[i][j] << ' ';
            }
            cout << endl;
        }*/
        cout << dp[n][k] << endl;
    }
    return 0;
}

F1题

这题虽然在后面但是其实思路是非常清晰的，我们使用邻接表建图(因为这样能节省空间)，然后开辟一个数组在建图的同时统计每个点的度数，找到最大点之后从最大点开始BFS，但是光BFS是不够的(并没有解决关键问题)，我们的关键问题是如何删掉那些多余的边。

这就要搬出我们的并查集了，我们在遍历顶点的开始先判断有路径的两个点是不是跟前面的点在一个集合，如果不是就将顶点加入并查集并直接输出两个点，如果是的话就略过，这样我们可以保证不会有多余的边出现(如果不理解并查集作用的请自行百度)。

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
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
const int maxn=200010;

vector<int> g[maxn];
int vis[maxn];

struct DisjoinSet{
    vector<int> father,rank;
    DisjoinSet(int n):father(n),rank(n){
        for(int i=0;i<n;i++)
            father[i]=i;
    }
    int find(int v){
        return father[v]=father[v]==v?v:find(father[v]);
    }
    void merge(int x,int y){
        int a=find(x),b=find(y);
        if(rank[a]<rank[b])
            father[a]=b;
        else{
            father[b]=a;
            if(rank[b]==rank[a])
                ++rank[a];
        }
    }
    bool same(int x,int y){
        return find(x)==find(y);
    }
};

void bfs(int u,int n){
    DisjoinSet set(n);
    queue<int> que;
    que.push(u);
    while(!que.empty()) {
        int t=que.front();que.pop();
        vis[t]=1;
        for(auto it = g[t].begin();it!= g[t].end();it++) {
            if(!vis[*it]) {
                que.push(*it);
                if (!set.same(t, *it)) {
                    set.merge(t, *it);
                    cout << t + 1 << ' ' << *it + 1 << endl;
                }
            }
        }
    }
}

int main(){
    int n,m;
    int count[maxn];
    ios::sync_with_stdio(false);
    while(cin>>n>>m){
        for(int i=0;i<n;i++)
            g[i].clear();
        memset(count,0,sizeof(count));
        memset(vis,0,sizeof(vis));
        int a,b;
        for(int i=0;i<m;i++){
            cin>>a>>b;
            a--;b--;
            count[a]++;count[b]++;
            g[a].push_back(b);
            g[b].push_back(a);
        }
        int mx_index=0,mx=0;
        for(int i=0;i<n;i++){
            if(count[i]>mx){
                mx=count[i];
                mx_index=i;
            }
        }
        bfs(mx_index,n);
    }
    return 0;
}

F2

F2等下次补坑吧哈哈哈哈