#13：人十我一Orz—

水题放送，写得依旧丑：

 #include <cstdio>

 #include <cstring>

 #include <cmath>

 #include <algorithm>

 #include <vector>

 using namespace std;

 const int INF = 2e9 + ;

 typedef long long ll;

 typedef pair<int, int> P;

 int H, G;

 ll f[][][];

 int dishg[][];

 int dish[], disg[];

 vector<P> hh, gg;

 int sqr(int x) {

     return x * x;

 }

 int dis(vector<P> v1, int i, vector<P> v2, int j) {

     return sqr(v1[i].first - v2[j].first) + sqr(v1[i].second - v2[j].second);

 }

 void init() {

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

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

             dishg[i][j] = dis(hh, i, gg, j);

     f[][][] = INF;

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

         dish[i] = dis(hh, i-, hh, i);

         f[i][][] = f[i-][][] + dish[i];

         f[i][][] = INF;

     }

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

         disg[j] = dis(gg, j-, gg, j);

         f[][j][] = INF;

         f[][j][] = INF;

     }

 }

 ll dp() {

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

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

             ll a = min(f[i-][j][] + dish[i], f[i-][j][] + dishg[i][j]);

             ll b = min(f[i][j-][] + dishg[i][j], f[i][j-][] + disg[j]);

             f[i][j][] = a;

             f[i][j][] = b;

         }

     }

     return f[H][G][];

 }

 int main() {

     scanf("%d%d", &H, &G);

     hh.push_back(P(, ));

     gg.push_back(P(, ));

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

         int x, y;

         scanf("%d%d", &x, &y);

         hh.push_back(P(x, y));

     }

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

         int x, y;

         scanf("%d%d", &x, &y);

         gg.push_back(P(x, y));

     }

     init();

     printf("%lld\n", dp());

     return ;

 }

BZOJ4745

 #include <cstdio>

 #include <cstring>

 #include <cmath>

 #include <algorithm>

 #include <vector>

 using namespace std;

 const int INF = 2e9 + ;

 typedef long long ll;

 typedef pair<int, int> P;

 int N, H, Delta;

 int f[][], eat[][];

 int pos1[];

 int dp() {

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

         int maxx = ;

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

             f[i][j] = f[i-][j];

             if (i > Delta) {

                 int t = i - Delta;

                 f[i][j] = max(f[i][j], f[t][pos1[t]]);

             }

             f[i][j] += eat[j][i];

             if (f[i][j] > maxx) {

                 maxx = f[i][j];

                 pos1[i] = j;

             }

         }

     }

     int ans = ;

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

         ans = max(ans, f[H][i]);

     return ans;

 }

 int main() {

     scanf("%d%d%d", &N, &H, &Delta);

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

         int ni, pos;

         for (scanf("%d", &ni); ni; ni--) {

             scanf("%d", &pos);

             eat[i][pos]++;

         }

     }

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

     return ;

 }

BZOJ1270

 #include <bits/stdc++.h>

 #define ri readint()

 #define gc getchar()

 #define ls p << 1

 #define rs p << 1 | 1

 using namespace std;

 typedef long long ll;

 const int maxn = ;

 int n, m;

 struct Seg {

     int l, r;

     bool fixed;

     ll sum;

 }t[maxn << ];

 inline int readint() {

     int x = , s = , c = gc;

     while (c <= )    c = gc;

     if (c == '-')    s = -, c = gc;

     for (; isdigit(c); c = gc)

         x = x *  + c - ;

     return x * s;

 }

 void build(int l, int r, int p) {

     t[p].l = l, t[p].r = r;

     if (l == r) {

         t[p].sum = ri;

         t[p].fixed = t[p].sum <= 1ll;

         return;

     }

     int mid = (l + r) >> ;

     build(l, mid, ls);

     build(mid+, r, rs);

     t[p].sum = t[ls].sum + t[rs].sum;

     t[p].fixed = t[ls].fixed && t[rs].fixed;

 }

 void Update(int l, int r, int p) {

     if (t[p].fixed)    return;

     if (t[p].l == t[p].r) {

         t[p].sum = sqrt(t[p].sum);

         t[p].fixed = t[p].sum <= 1ll;

         return;

     }

     int mid = (t[p].l + t[p].r) >> ;

     if (l <= mid)    Update(l, r, ls);

     if (mid < r)    Update(l ,r, rs);

     t[p].sum = t[ls].sum + t[rs].sum;

     t[p].fixed = t[ls].fixed && t[rs].fixed;

 }

 ll Query(int l, int r, int p) {

     if (l <= t[p].l && t[p].r <= r)

         return t[p].sum;

     int mid = (t[p].l + t[p].r) >> ;

     ll res = 0ll;

     if (l <= mid)    res += Query(l, r, ls);

     if (mid < r)    res += Query(l, r, rs);

     return res;

 }

 int main() {

     n = ri;

     build(, n, );

     for (m = ri; m; m--) {

         int x = ri, l = ri, r = ri;

         if (x == ) {

             printf("%lld\n", Query(l, r, ));

         } else {

             Update(l, r, );

         }

     }

     return ;

 }

BZOJ3211

cf818E，计数不一定非要乘法原理，枚举标杆累加。此题性质符合尺取，l和r可不断后移。

 #include <bits/stdc++.h>

 using namespace std;

 const int maxn = 1e5 + ;

 int n, k, a[maxn];

 int pri[], cnt[], t;

 int b[maxn][];

 void div(int k) {

     for (int i = ; i * i <= k; i++) {

         if (k % i == ) {

             pri[++t] = i;

             while (k % i == ) {

                 k /= i;

                 cnt[t]++;

             }

         }

     }

     if (k > ) {

         pri[++t] = k;

         cnt[t] = ;

     }

 }

 long long two_point() {

     int l = , r = ;

     long long ans = ;

     while (l <= n) {

         bool valid = false;

         while (r < n && !valid) {

             r++;

             valid = true;

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

                 valid &= (b[r][j] - b[l-][j]) >= cnt[j];

         }

         if (!valid)    break;

         while (l <= r && valid) {

             ans += n - r + ;

             l++;

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

                 valid &= (b[r][j] - b[l-][j]) >= cnt[j];

         }

     }

     return ans;

 }

 int main() {

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

     div(k);

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

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

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

             while (a[i] % pri[j] == ) {

                 a[i] /= pri[j];

                 b[i][j]++;

             }

             b[i][j] += b[i-][j];

         }

     }

     cout << two_point() << endl;

     return ;

 }

cf818F，我强猜一下结论的原因：难道是因为完全图边多、链桥多，所以边多桥多就凑一起？

 #include <bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 int q;

 ll n;

 ll judge(ll k) {

     return n - k + min(n - k, (k*k - k) / );

 }

 int main() {

     ios_base::sync_with_stdio(false);

     cin.tie();

     for (cin >> q; q; q--) {

         cin >> n;

         ll l = , r = n;

         while (l < r-) {

             ll lmid = (l + r) >> ;

             ll rmid = (lmid + r) >> ;

             if (judge(lmid) < judge(rmid))

                 l = lmid;

             else    r = rmid;

         }

         cout << max(judge(r), judge((l + r) >> )) << "\n";

     }

     return ;

 }

cf822D，遍历素因子的技巧值得学习。以及貌似第一发猜的结论好像是对的但是我写挂了……but还是正解优雅。

 #include <bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const int maxn = 5e6 + ;

 const int mod = 1e9 + ;

 const ll INF = 1e18;

 int t, l, r;

 ll f[maxn];

 int primes[maxn];

 void init() {

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

         primes[i] = i;

         f[i] = INF;

     }

     for (int i = ; i * i <= r; i++) {//不采集素数时不需遍历maxn

         if (primes[i] == i) {

             for (int j = i * i; j <= r; j += i)

                 primes[j] = min(primes[j], i);

         }

     }

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

         for (int j = i; j != ; j /= primes[j]) {//遍历素因子

             f[i] = min(f[i], f[i / primes[j]] + 1LL * i * (primes[j] - ) / 2LL);

         }

     }

 }

 int main() {

     scanf("%d%d%d", &t, &l, &r);

     init();

     ll ans = , tt = ;

     for (int i = l; i <= r; i++) {

         f[i] %= mod;

         ans = (ans + tt * f[i]) % mod;

         tt = tt * t % mod;

     }

     cout << ans << endl;

     return ;

 }

巴特西

#13：人十我一Orz——6

最新文章

热门文章