队内训练赛二

时间：2021-07-22 22:14:31

记录一个菜逼的成长。。

A:ZOJ3158 Cut The Cake
题目大意:
给你一个m*n的矩阵，从上到下把它划分成两个子矩阵，两个子矩阵满足值的和的差不超过k，求最小的差值。
Note：不能在第一列的左边和最后一列的右边切。

由于m,n值小，我们可以枚举切的位置直接搜索。在这之前我们要先预处理一下每一行的前缀和。方便搜索时记录最小值。

#include <bits/stdc++.h>
using namespace std;
#define ALL(v) (v).begin(),(v).end()
#define cl(a,b) memset(a,b,sizeof(a))
#define clr clear()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
typedef long long LL;
const int INF = 0x3f3f3f3f;
const int maxn = 10 + 10;
LL a[maxn][maxn];
LL sum[maxn][maxn];
int n,m;
LL k,mn,tot;
void dfs(int dep,int s)
{
if(dep == n+1){
        mn = min(mn,abs(tot-2*s));
return ;
    }
for( int i = 1; i < m; i++ ){
        dfs(dep+1,s+sum[dep][i]);
    }
}
int main()
{
while(~scanf("%d%d",&n,&m)){
        cl(sum,0);tot = 0;
for( int i = 1; i <= n; i++ ){
for( int j = 1; j <= m; j++ ){
scanf("%lld",&a[i][j]);
                sum[i][j] = sum[i][j-1] + a[i][j];
                tot += a[i][j];
            }
        }
scanf("%lld",&k);
        mn = (1LL<<62);
        dfs(1,0);
if(mn > k){
puts("You'd better buy another one!");
        }
else printf("%lld\n",mn);
    }
return 0;
}

B:HDU 5685 Problem A
一眼看去。线段树的区间查询。

#include <bits/stdc++.h>
using namespace std;
#define ALL(v) (v).begin(),(v).end()
#define cl(a,b) memset(a,b,sizeof(a))
#define clr clear()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define lson t<<1,l,mid
#define rson t<<1|1,mid+1,r
typedef long long LL;
typedef pair<int,int> PII;
const int INF = 0x3f3f3f3f;
const int maxn = 100000 + 10;
char str[maxn];
struct Node{
int l,r,v;
}node[maxn<<2];
void pushup(int t)
{
    node[t].v = node[t<<1].v * node[t<<1|1].v % 9973;
}
void build(int t,int l,int r)
{
    node[t].l = l;
    node[t].r = r;
if(l == r){
        node[t].v = str[l-1] - 28;
return ;
    }
int mid = (l + r) >> 1;
    build(lson);
    build(rson);
    pushup(t);
}
int query(int t,int l,int r)
{
if(l <= node[t].l && r >= node[t].r){
return node[t].v;
    }
int mid = (node[t].l + node[t].r) >> 1;
int ret = 1;
if(l <= mid)ret = ret * query(t<<1,l,r) % 9973;
if(r > mid)ret = ret * query(t<<1|1,l,r) % 9973;
return ret % 9973;
}
int main()
{
int n;
while(~scanf("%d",&n)){
scanf("%s",str);
        build(1,1,strlen(str));
for( int i = 1; i <= n; i++ ){
int l,r;
scanf("%d%d",&l,&r);
printf("%d\n",query(1,l,r));
        }
    }
return 0;
}

C:HDU 5686 Problem B
列出前几个，会发现是斐波那契数列。
你可以写Java大数，也可以用C的数组模拟。

import java.util.*;
import java.math.*;
public class Main {

public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        BigInteger []fib = new BigInteger[201];
        fib[1] = BigInteger.ONE;
        fib[2] = BigInteger.valueOf(2);
for( int i = 3; i < 201; i++ ){
            fib[i] = fib[i-1].add(fib[i-2]);
        }
while(cin.hasNext()){
int n = cin.nextInt();
            System.out.println(fib[n]);
        }

    }

}

D:见这里

E:ZOJ3166 Lazy Tourist
题目大意:
有n个城市，其中有c个城市有旅馆。
有m条路径。
问从哪个旅馆出发再次回到这个旅馆的距离最短，若有多个答案输出编号最小的城市编号。

由于n最大到100，我们可以用floyd把所有的最短距离求出。
这里注意初始化时要将到旅馆所在的城市设为INF，而不是0，要将旅馆所在的城市设为终点。就是 dis[c[i]][c[i]]=INF;
因为要从旅馆出来，最后求的也是 dis[c[i]][c[i]] 。
那么最后我们只要记录 dis[c[i]][c[i]] 最小的 c[i] 即可。

#include <bits/stdc++.h>
using namespace std;
#define ALL(v) (v).begin(),(v).end()
#define cl(a,b) memset(a,b,sizeof(a))
#define clr clear()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
typedef long long LL;
const int INF = 0x3f3f3f3f;
const int maxn = 100 + 10;
int dis[maxn][maxn],cc[maxn];
int main()
{
int n,c;
while(~scanf("%d%d",&n,&c)){
for( int i = 1; i <= n; i++ ){
for( int j = 1; j <= n; j++ ){
                dis[i][j] = INF;
            }
        }
for( int i = 1; i <= c; i++ )scanf("%d",cc+i);
int m;
scanf("%d",&m);
while(m--){
int u,v,d;
scanf("%d%d%d",&u,&v,&d);
            dis[u][v] = min(d,dis[u][v]);
        }
for( int k = 1; k <= n; k++ ){
for( int i = 1; i <= n; i++ ){
for( int j = 1; j <= n; j++ ){
                    dis[i][j] = min(dis[i][j],dis[i][k] + dis[k][j]);
                }
            }
        }
int ans = -1,mn = INF;
for( int i = 1; i <= c; i++ ){
if(mn > dis[cc[i]][cc[i]]){
                mn = dis[cc[i]][cc[i]];
                ans = cc[i];
            }
        }
if(ans != -1)printf("%d\n",ans);
else puts("I will nerver go to that city!");
    }
return 0;
}

F:ZOJ3167 Find 7 Faster Than John Von Neumann
题目大意：
给你k,m,求n满足 mn 的第k位为7。

直接用高精度模拟。

#include <bits/stdc++.h>
using namespace std;
#define ALL(v) (v).begin(),(v).end()
#define cl(a,b) memset(a,b,sizeof(a))
#define clr clear()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
typedef long long LL;
const int INF = 0x3f3f3f3f;
const int maxn = 10000 + 10;
char a[maxn];
int main()
{
int k,m;
while(~scanf("%d%d",&k,&m)){
        cl(a,0);
int ind = 0,t = m;
while(t){
            a[ind++] = t % 10;
            t /= 10;
        }
int ans = 0,tmp = 0;
while(a[k-1] != 7){
            ans++;tmp = 0;
for( int i = 0; i < ind; i++ ){
                tmp = a[i]*m + tmp;
                a[i] = tmp % 10;
                tmp /= 10;
            }
while(tmp){
                a[ind++] = tmp % 10;
                tmp /= 10;
            }
        }
        printf("%d\n",ans+1);
    }
return 0;
}

G:ZOJ3278 8G Island
题目大意:
给你两个序列，一个有n个数，一个m个数，问这两个序列相乘后的第k大的数是什么。

数据范围比较大。显然寻常方法不行。
我们试试二分。
将两个序列排序。
二分第K大的数。
对于每一个二分的数判断比它大的数有多少个。
判断时我们可以从一个序列的最大值开始枚举，接着在枚举另一个序列的最小值。一旦 a[i]∗b[j]>=x ，我们可以马上统计数量 m−j ;
如果返回的数量大于k保存二分值，继续二分。

#include <bits/stdc++.h>
using namespace std;
#define ALL(v) (v).begin(),(v).end()
#define cl(a,b) memset(a,b,sizeof(a))
#define clr clear()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
typedef long long LL;
const int INF = 0x3f3f3f3f;
const int maxn = 100000 + 10;
LL a[maxn],b[maxn];
int n,m;
LL k;
LL check(LL x)
{
    LL ret = 0;
for( int i = n-1,j = 0; i >= 0; i-- ){
for( ; j < m; j++ ){
if(a[i] * b[j] >= x){
                ret += m - j;
break;
            }
        }
    }
return ret;
}
int main()
{
while(~scanf("%d%d%lld",&n,&m,&k)){
for( int i = 0; i < n; i++ )scanf("%lld",a+i);sort(a,a+n);
for( int i = 0; i < m; i++ )scanf("%lld",b+i);sort(b,b+m);
        LL l = a[0] * b[0];
        LL r = a[n-1] * b[m-1];
        LL ans = 0;
while(l <= r){
            LL mid = (l + r) >> 1;
if(check(mid) >= k){
                l = mid + 1;
                ans = mid;
            }
else r = mid - 1;
        }
printf("%lld\n",ans);
    }
return 0;
}

PS:后面四题是cf div2的AB题，为了练习切水题的1y率

H:codeforces787A-The Monster
题目大意:
给你a,b,c,d;
X = b + ax;
Y = d + cy;
求最小的X使得X == Y

暴力枚举x,y

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
int main()
{
int a,b,c,d;
while(~scanf("%d%d%d%d",&a,&b,&c,&d)){
for( int i = 0; i <= 1000; i++ ){
for( int j = 0; j <= 1000; j++ ){
if(a * i == c * j + d - b){
printf("%d\n",a * i + b);
return 0;
                }
            }
        }
printf("%d\n",-1);
    }
return 0;
}

I:codeforces787B-Not Afraid
题目大意:
有n个星球，m个组，每个星球有两个人，编号i,-i，分属不同阵营
给出每个组的成员编号，可重复
如果一个组里有k个星球的人，但是每个星球只有一人，则输出YES，否则NO

用个数组统计即可，注意一下编号可重复

#include <bits/stdc++.h>
using namespace std;
#define ALL(v) (v).begin(),(v).end()
#define cl(a,b) memset(a,b,sizeof(a))
#define clr clear()
#define pb push_back
typedef long long LL;
const int INF = 0x3f3f3f3f;
const int maxn = 20000 + 10;
int vis[maxn];
int main()
{
int n,m;
while(~scanf("%d%d",&n,&m)){
bool ans = false;
for( int i = 0; i < m; i++ ){
int k;scanf("%d",&k);cl(vis,0);
bool flag = true;
for( int j = 0; j < k; j++ ){
int x;
scanf("%d",&x);
if(x < 0)x = -x,x += 10000;
                vis[x]++;
if(x > 10000){
if(vis[x] && vis[x-10000])flag = false;
                }
else {
if(vis[x] && vis[x+10000])flag = false;
                }
            }
if(flag)ans = true;
        }
puts(ans ? "YES" : "NO");
    }
return 0;
}

J:codeforces792A-New Bus Route
题目大意：
有n个点，对应有n个值。
求最小差的绝对值和数量

一开始看n的范围这么大，直接暴力n^2肯定T
后来一想，只要排序一下，求相邻的值就可以了。

#include <bits/stdc++.h>
using namespace std;
#define ALL(v) (v).begin(),(v).end()
#define cl(a,b) memset(a,b,sizeof(a))
#define clr clear()
#define pb push_back
typedef long long LL;
const int INF = 0x3f3f3f3f;
const int maxn = 200000 + 10;
int a[maxn];
int main()
{
int n;
while(~scanf("%d",&n)){
for( int i = 0; i < n; i++ ){
scanf("%d",a+i);
        }
        sort(a,a+n);
int mn = 2*INF,ans = 0;
for( int i = 1; i < n; i++ ){
if(mn > a[i] - a[i-1]){
                mn = a[i] - a[i-1];
                ans = 1;
            }
else if(mn == a[i] - a[i-1])ans++;
        }
printf("%d %d\n",mn,ans);
    }
return 0;
}

K:codeforces792B-Counting-out Rhyme
题目大意:
有n个人，有k轮，每轮一个 ki 值
每一轮有一个领导者，从领导者的后一个开始数，数到第 ki 个出局
如此重复，输出每轮出局人的编号

用vector模拟。我们可以用 ki 加上当前第一个数的人的前面的人数，表示每一轮都从第一个开始数。

#include <bits/stdc++.h>
using namespace std;
#define ALL(v) (v).begin(),(v).end()
#define cl(a,b) memset(a,b,sizeof(a))
#define clr clear()
#define pb push_back
typedef long long LL;
const int INF = 0x3f3f3f3f;
const int maxn = 100 + 10;
vector<int>a;
int s[maxn];
int main()
{
int n,k;
while(~scanf("%d%d",&n,&k)){
        a.clr;
for( int i = 1; i <= n; i++ )a.pb(i);
for( int i = 1; i <= k; i++ )scanf("%d",s+i);
int st = 1;
for( int i = 1; i <= k; i++ ){
int step = s[i];
            step += st;
            step %= a.size();step = (step-1+a.size()) % a.size();
printf("%d ",a[step]);
            a.erase(a.begin()+step);
            st = (step + 1) % a.size();
        }
    }
return 0;
}
标签：

相关文章