codeforce 379(div.2)

A、B略

C题 ——贪心，二分查找：

对于每一个a[i]，在d中二分查找 s-b[i]，注意不要忘记计算速度为x时需要花费的最小时间，以及整数范围为64位整数

 1 #include <cstdio>

 2 #include <algorithm>

 3 #include <cstring>

 4

 5 using namespace std;

 6 const int maxn = 2*100000+10;

 7 typedef long long LL;

 8

 9 int n, m, k;

10 int x, s;

11 int a[maxn], b[maxn], c[maxn], d[maxn];

12

13 int main() {

14     scanf("%d%d%d", &n, &m, &k);

15     scanf("%d%d", &x, &s);

16     a[0] = x;

17     b[0] = 0;

18     for(int i = 1; i <= m; i++) scanf("%d",&a[i]);

19     for(int i = 1; i <= m; i++) scanf("%d",&b[i]);

20     for(int i = 0; i < k; i++) scanf("%d",&c[i]);

21     for(int i = 0; i < k; i++) scanf("%d",&d[i]);

22     LL  ans = LL(n)*x;

23     for(int i = 0; i <=  m; i++) {

24         if(b[i] <= s) {

25             int temp = b[i];

26             int tt = upper_bound(d, d+k, s - temp) - d;

27             if(tt) {

28                 tt--;

29                 LL  as = n - c[tt] > 0 ? LL(n - c[tt]) * a[i] : 0;

30                 ans = min(ans, as);

31             }

32             else {

33                 LL  as = LL(n) * a[i];

34                 ans = min(ans, as);

35             }

36         }

37     }

38     printf("%I64d\n", ans);

39 }

D 思路很简单，注意细节即可

  1 #include <cstdio>

  2 #include <vector>

  3 #include <algorithm>

  4 #include <cstring>

  5 #include <cstdlib>

  6 #include <cmath>

  7 using namespace std;

  8 const int maxn = 500000+10;

  9

 10 struct P{

 11     char ch;

 12     double dist;

 13     P(char c, double d): ch(c), dist(d){}

 14     bool operator < (const P& b)const {

 15         return dist < b.dist;

 16     }

 17 };

 18 vector<P> dig1, dig2, dig3, dig4;

 19 vector<P> ver1, ver2, ver3, ver4;

 20

 21 int n;

 22 int x0, y0_;

 23 #define y0  y0_

 24 void ins(char c, int dx, int dy) {

 25     if(dx == dy) {

 26         if(dx > 0) {

 27             double dis = sqrt(double(dy)*dy + double(dx)*dx);

 28             dig1.push_back(P(c, dis));

 29         }

 30         if(dx < 0) {

 31             double dis = sqrt(double(dy)*dy + double(dx)*dx);

 32             dig3.push_back(P(c, dis));

 33

 34         }

 35     }

 36     if(dx == -dy) {

 37         if(dx > 0) {

 38             double dis = sqrt(double(dy)*dy + double(dx)*dx);

 39             dig4.push_back(P(c, dis));

 40         }

 41         if(dx < 0) {

 42             double dis = sqrt(double(dy)*dy + double(dx)*dx);

 43             dig2.push_back(P(c, dis));

 44

 45         }

 46     }

 47     if(dy == 0){

 48         if(dx > 0) {

 49             double dis = sqrt(double(dy)*dy + double(dx)*dx);

 50             ver1.push_back(P(c,dis));

 51         }

 52         if(dx < 0) {

 53             double dis = sqrt(double(dy)*dy + double(dx)*dx);

 54             ver3.push_back(P(c,dis));

 55

 56         }

 57     }

 58     if(dx == 0){

 59         if(dy > 0) {

 60             double dis = sqrt(double(dy)*dy + double(dx)*dx);

 61             ver2.push_back(P(c, dis));

 62         }

 63         if(dy < 0) {

 64             double dis = sqrt(double(dy)*dy + double(dx)*dx);

 65             ver4.push_back(P (c, dis));

 66         }

 67     }

 68 }

 69 int main () {

 70     scanf("%d", &n);

 71     scanf("%d%d", &x0, &y0);

 72     for(int i = 0; i < n; i++) {

 73         char ch;

 74         int xx, yy;

 75         getchar();

 76         scanf("%c%d%d", &ch, &xx, &yy);

 77         int dy = yy - y0, dx = xx - x0;

 78         ins(ch , dx, dy);

 79     }

 80     sort(dig1.begin(), dig1.end());

 81     sort(dig2.begin(), dig2.end());

 82     sort(dig3.begin(), dig3.end());

 83     sort(dig4.begin(), dig4.end());

 84     sort(ver1.begin(), ver1.end());

 85     sort(ver2.begin(), ver2.end());

 86     sort(ver3.begin(), ver3.end());

 87     sort(ver4.begin(), ver4.end());

 88     if(dig1.size()) {

 89         if(dig1[0].ch == 'Q' ||  dig1[0].ch == 'B') {

 90             printf("YES\n");

 91             return 0;

 92         }

 93     }

 94     if(dig2.size()) {

 95         if(dig2[0].ch == 'Q' ||  dig2[0].ch == 'B') {

 96             printf("YES\n");

 97             return 0;

 98         }

 99     }

100     if(dig3.size()) {

101         if(dig3[0].ch == 'Q' ||  dig3[0].ch == 'B') {

102             printf("YES\n");

103             return 0;

104         }

105     }

106     if(dig4.size()) {

107         if(dig4[0].ch == 'Q' ||  dig4[0].ch == 'B') {

108             printf("YES\n");

109             return 0;

110         }

111     }

112     if(ver1.size()) {

113         if(ver1[0].ch == 'Q' || ver1[0].ch == 'R') {

114             printf("YES\n");

115             return 0;

116         }

117     }

118

119     if(ver2.size()) {

120         if(ver2[0].ch == 'Q' || ver2[0].ch == 'R') {

121             printf("YES\n");

122             return 0;

123         }

124     }

125     if(ver3.size()) {

126         if(ver3[0].ch == 'Q' || ver3[0].ch == 'R') {

127             printf("YES\n");

128             return 0;

129         }

130     }

131     if(ver4.size()) {

132         if(ver4[0].ch == 'Q' || ver4[0].ch == 'R') {

133             printf("YES\n");

134             return 0;

135         }

136     }

137     printf("NO\n");

138     return 0;

139

140 }

E题：首先使用并查集将相同颜色的结点缩成一点，此时树中结点黑白相间，只需要求出树的直径（最长路）除以2就是答案。

 #include <cstdio>

 #include <cstring>

 #include <vector>

 #include <algorithm>

 #include <queue>

 using namespace std;

 const int maxn = +;

 vector<int> G[maxn];

 void add(int v, int u) {

     G[v].push_back(u);

     G[u].push_back(v);

 }

 int n;

 int col[maxn];

 int col2[maxn];

 int vis[maxn];

 int pa[maxn];

 int findpa(int x) {return x == pa[x] ? x : pa[x] = findpa(pa[x]);}

 int from, ans;

 void dfs(int u, int v, int d) {

     if(d > ans) {

         ans = d;

         from = v;

     }

     for(int i =  ; i< G[v].size(); i++) {

         int z = G[v][i];

         if(z != u) {

             dfs(v, z, d+);

         }

     }

 }

 int U[maxn];

 int V[maxn];

 int main() {

     scanf("%d", &n);

     for(int i = ; i <= n; i++)

         scanf("%d", &col[i]);

     for(int i = ; i < n; i++)

         scanf("%d%d", &U[i], &V[i]);

     for(int i = ; i <= n; i++) pa[i] = i;

     for(int i = ; i <= n; i++) {

         int fu = findpa(U[i]);

         int fv = findpa(V[i]);

         if(col[fu] == col[fv]) {

             pa[fu] = fv;

         }

     }

     for(int i = ; i <= n; i++) {

         int fu = findpa(U[i]);

         int fv = findpa(V[i]);

         if(col[fu] != col[fv]) {

             add(fu, fv);

         }

     }

     ans = -;

     int u = pa[];

     for(int i = ; i < G[u].size(); i++) {

         int v = G[u][i];

         dfs(u, v, );

     }

     u = from;

     for(int i = ; i < G[u].size(); i++) {

         int v = G[u][i];

         dfs(u, v, );

     }

     ans = (ans+)/;

     printf("%d\n", ans);

 }

F题：注意到 a&b + a|b = a+b

即可根据数组b， c的定义求出a，然后用求出的a反推数组b，c判断是否是解

详见代码：

 #include <iostream>

 #include <algorithm>

 #include <cstring>

 using namespace std;

 const int maxn =  + ;

 typedef long long LL;

 LL  a[maxn], b[maxn], c[maxn];

 int num[];

 int n;

 int main() {

     ios::sync_with_stdio(false);

     cin >> n;

     for(int i = ; i < n; i++) cin >> b[i];

     for(int i = ; i < n; i++) cin >> c[i];

     LL sum = ;

     for(int i = ; i < n; i++) {

         a[i] = b[i] + c[i];

         sum += a[i];

     }

     if(sum % (*n)) {

         cout << - << endl;

         return ;

     }

     sum /= *n;

     for(int i = ; i < n; i++) {

         a[i] = (a[i] - sum);

         if(a[i] % n) {

             cout << - << endl;

             return ;

         }

         else{

             a[i] /= n;

         }

     }

     for(int i = ; i < n; i++) {

         LL temp = a[i];

         for(int j = ; j < ; j++) {

             num[j] += temp%;

             temp /= ;

         }

     }

     for(int i = ; i < n; i++) {

         LL b_ = , c_ = ;

         for(int j = ; j < ; j++) {

             if(a[i] & (1LL << j)) {

                 b_ += num[j] * (1LL << j);

                 c_ += n * (1LL << j);

             }

             else c_ += num[j] * (1LL << j);

         }

         if(b_ != b[i] || c_ != c[i]) {

                 cout << - << endl;

                 return ;

         }

     }

     cout << a[];

     for(int i = ; i < n; i++) {

         cout << " " << a[i];

     }

     cout << endl;

     return ;

 }

巴特西

codeforce 379(div.2)

最新文章

热门文章