indeed 5.13 第二次网测

题目描述，我找不见了，大概写一下想法和代码吧。

1. 没有看

2. 由于数据范围很小，就是简单的枚举，求全排列，然后更新答案。

 #include<bits/stdc++.h>

 #define pb push_back

 typedef long long ll;

 using namespace std;

 typedef pair<int, int> pii;

 const int maxn = 1e3 + ;

 int n, k, m;

 int a[], b[], u[];

 bool ina[], inb[];

 int work() {

     int r = ;

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

         if(ina[a[i] ] && ina[b[i] ])

             r += u[i];

         if(inb[a[i] ] && inb[b[i] ])

             r += u[i];

     }

     return r;

 }

 void solve() {

     cin >> n >> k >> m;

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

         cin >> a[i] >> b[i] >> u[i];

     }

     vector<int> p;

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

         p.push_back(i);

     int res = ;

     do {

         memset(ina, , sizeof ina);

         memset(inb, , sizeof inb);

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

             ina[p[i] ] = ;

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

             inb[p[i] ] = ;

         res = max(res, work());

     } while(next_permutation(p.begin(), p.end()));

     cout << res << endl;

 }

 int main() {

     freopen("test.in", "r", stdin);

     //freopen("test.out", "w", stdout);

     ios::sync_with_stdio();

     cin.tie(); cout.tie();

     solve();

     return ;

 }

3. 这次第三题挺有意思的，求左上角到右下角的最短路径，但是多了一种跳的操作。

我的想法很简单，由于在每一个点上都可以选择跳与不跳，而且只能一次跳，那就预处理出每个点到起始点的距离，每个点到终点的距离，然后遍历每一个点，更新答案。

一个是这个点到起点的距离加上到终点的距离，一个是这个点到起点的距离 + 1（完成跳的动作） + 跳之后的点到终点的距离。更新答案。

 #include<bits/stdc++.h>

 #define pb push_back

 typedef long long ll;

 using namespace std;

 typedef pair<int, int> pii;

 const int maxn = 1e3 + ;

 const int inf = 1e5;

 int h, w, d, r;

 string a[];

 int sdis[][], edis[][];

 int dx[] = {, , , -};

 int dy[] = {, -, , };

 bool check(int x, int y) {

     if(x <  || x >= h || y <  || y >= w) return ;

     return ;

 }

 void dfs(int x, int y, int v) {

     sdis[x][y] = v;

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

         int cx = x + dx[i], cy = y + dy[i];

         if(check(cx, cy) && a[cx][cy] != '#' && sdis[cx][cy] > v + ) {

             dfs(cx, cy, v + );

         }

     }

 }

 void dfs1(int x, int y, int v) {

     edis[x][y] = v;

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

         int cx = x + dx[i], cy = y + dy[i];

         if(check(cx, cy) && a[cx][cy] != '#' && edis[cx][cy] > v + ) {

             dfs1(cx, cy, v + );

         }

     }

 }

 void solve() {

     cin >> h >> w >> d >> r;

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

         cin >> a[i];

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

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

             sdis[i][j] = edis[i][j] = inf;

     }

     dfs(, , );

     dfs1(h - , w - , );

     int res = inf;

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

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

             int t1 = sdis[i][j] + edis[i][j];

             res = min(res, t1);

             int x = i + d, y = j + r;

             if(check(x, y)) {

                 int t2 = sdis[i][j] + edis[x][y] + ;

                 res = min(res, t2);

             }

         }

     }

     if(res == inf) res = -;

     cout << res << endl;

 }

 int main() {

     freopen("test.in", "r", stdin);

     //freopen("test.out", "w", stdout);

     ios::sync_with_stdio();

     cin.tie(); cout.tie();

     solve();

     return ;

 }

4. 目标函数是差的绝对值乘以权值之和，考虑权值都相等的时候，这时候的最佳点就是中间的那个点（奇数个点是中间点，偶数个点是中间2个点之间的点都行）。

下面考虑权值r不相等的时候，这个函数其实是凹的，这个性质很重要，可以进行二分查找，目标点是该点比它左右2点的函数值都要小，如果该点比左边大，比右边小，那查找区间往左移动，否则往右移动。

 #include<bits/stdc++.h>

 #define pb push_back

 typedef long long ll;

 using namespace std;

 typedef pair<int, int> pii;

 const int maxn = 1e5 + ;

 ll len;

 int n;

 ll a[maxn];

 int r[maxn];

 ll work(ll x) {

     ll res = ;

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

         res += abs(a[i] - x) * r[i];

     }

     return res;

 }

 void solve() {

     scanf("%lld%d", &len, &n);

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

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

     }

     ll left = , right = len;

     ll res = -;

     while(left < right) {

         ll mid = (left + right) / ;

         ll r = work(mid);

         ll r1 = work(mid - );

         ll r2 = work(mid + );

         if(r <= r1 && r <= r2) {

             left = right = mid;

             break;

         } else if(r1 <= r && r <= r2) {

             right = mid - ;

         } else if(r1 >= r && r >= r2) {

             left = mid + ;

         }

     }

     if(left < ) left++;

     if(left > len) left--;

     printf("%lld\n", work(left));

 }

 int main() {

     freopen("test.in", "r", stdin);

     //freopen("test.out", "w", stdout);

     solve();

     return ;

 }

巴特西

indeed 5.13 第二次网测

最新文章

热门文章