2019 牛客 多校赛 第七场
slove 4/11
rank 328
补题 7/11
--------------------------------------------------------
link
A、String
贪心暴力跑最长符合条件的，签到
#include <bits/stdc++.h>
using namespace std;
char s[205];
int str[205];
string ans[205];
int num1[205], num0[205], num[205];
int main()
{
int T;
scanf("%d", &T);
while (T--)
{
scanf("%s", s);
memset(str, 0, sizeof(str));
memset(num, 0, sizeof(num));
memset(num1, 0, sizeof(num1));
memset(num0, 0, sizeof(num0));
int tot = 0;
int len = strlen(s);
/*第一次预处理*/
for (int i = 0; i < len;)
{
if (s[i] == '1')
{
str[++tot] = 1;
while (s[i] == '1' && i < len)
{
num[tot]++;
i++;
}
}
else
{
str[++tot] = 0;
while (s[i] == '0' && i < len)
{
num[tot]++;
i++;
}
}
}
/*第二次*/
int start = -1, idx;
int Len = -1;
for (int i = 1; i <= tot;)
{
if (start == -1)
{
start = str[i];
idx = i;
}
if (start == 1)
{
++Len;
ans[Len] = "";
for (int j = 1; j <= num[idx]; j++)
ans[Len] += '1';
num1[Len] = num[idx];
i++;
start = -1;
}
else
{
++Len;
ans[Len] = "";
for (int j = 1; j <= num[idx]; j++)
ans[Len] += '0';
num0[Len] = num[idx];
++i;
for (int j = 1; j <= num[i]; j++)
ans[Len] += '1';
num1[Len] = num[i];
++i;
start = -1;
}
}
vector<string>v;
for (int i = 0; i <= Len;)
{
string t = ans[i];
int f = i;
int j = i + 1;
bool ff = true;
for (; j <= Len; j++)
{
if (num1[j] == 0)
{
break;
}
else if (num0[f] > num0[j])
{
t += ans[j];
ff = false;
}
else if (num0[f] == num0[j] && (num1[f] < num1[j] || (num1[f] == num1[j] && ff == true)))
{
t += ans[j];
if (num1[f] != num1[j])
ff = false;
}
else
break;
}
i = j;
v.push_back(t);
}
len = v.size();
for (int i = 0; i < len; i++)
{
cout << v[i];
printf("%c", i == len - 1 ? '\n' : ' ');
}
}
}
B、Irreducible Polynomial
判断一个多项式是否可以被分解
最高次方大于等于3的一定可以被分解，最高次方小于2的一定不能被分解。最高次方等于2的，有解就可以被分解，否则，不可以被分解。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a[100];
int n;
int main()
{
int T;
scanf("%d", &T);
while (T--)
{
scanf("%d", &n);
for (int i = n; i >= 0; i--)
{
scanf("%lld", &a[i]);
}
if (n >= 3)
printf("No\n");
else if (n == 2)
{
ll deta = a[1] * a[1] - 4 * a[0] * a[2];
if (deta >= 0)
printf("No\n");
else
printf("Yes\n");
}
else if (n == 1 || n == 0)
{
printf("Yes\n");
}
}
return 0;
} C、Governing sand
有很多种树，他们的高度，移除所花费的代价，数量已知，现在希望让最高的树的数量严格大于其他树的数量，问移除树需要花费的最小代价。
权值线段树求区间前K小，赛事更新操作没写 + 号，数量没用 ll ，难受啊，本来5题了
1、首先考虑将高度离散化，并且统计小于等于某高度的树的数量，和移除这些树的总代价
2、考虑枚举每一种高度作为最高高度，我们可以 O(1) 算出删除所有比他高的数目的总代价，并且可以知道需要留多少颗高度小于他的树
3、于是题目就变成了，求区间前K小，
4、注意需要保证在所有同一高度的数木全部加入到区间中才更新答案，否则，若最高高度的树删除的代价最小，可以会删最高高度的树，但显然这是不合法的。
5、题目给的代价的范围是1-200，赛时没注意，所以也可以遍历找最小代码，但如果代价是1e9，那么就只能权值线段树维护区间前 K 小和了。
#include <bits/stdc++.h>
#define ll long long
#define lson left,mid,k<<1
#define rson mid+1,right,k<<1|1
#define imid int mid=(left+right)/2;
using namespace std;
const int MAXN = 2e5 + 5;
struct note
{
ll h;
ll val;
ll num;
}in[MAXN];
ll t[MAXN];
ll num[MAXN];
ll money[MAXN];
struct node
{
int l;
int r;
ll cnt;
ll sum;
ll val;
}que[MAXN * 4];
int ql, qr;
ll val;
void up(int k)
{
que[k].sum = que[k << 1].sum + que[k << 1 | 1].sum;
que[k].cnt = que[k << 1].cnt + que[k << 1 | 1].cnt;
}
void build(int left, int right, int k)
{
que[k].l = left;
que[k].r = right;
if (left == right)
{
que[k].cnt = 0;
que[k].val = 0;
que[k].sum = 0;
return;
}
imid;
build(lson);
build(rson);
up(k);
}
void update(int left, int right, int k)
{
if (qr < left || right < ql)
return;
if (ql <= left && right <= qr)
{
que[k].cnt += in[val].num;
que[k].val = t[in[val].val];
que[k].sum = que[k].cnt * que[k].val;
return;
}
imid;
update(lson);
update(rson);
up(k);
}
ll query(int left, int right, int k, ll val)
{
if (left == right)
{
return min((ll)val, que[k].cnt) * que[k].val;
}
imid;
if (val <= que[k << 1].cnt)
{
return query(lson, val);
}
else if (val > que[k << 1].cnt)
{
val -= que[k << 1].cnt;
return que[k << 1].sum + query(rson, val);
}
}
int main()
{
int n;
while (scanf("%d", &n) > 0)
{
for (int i = 1; i <= n; i++)
{
num[i] = 0;
money[i] = 0;
scanf("%lld%lld%lld", &in[i].h, &in[i].val, &in[i].num);
t[i] = in[i].h;
}
sort(t + 1, t + 1 + n);
int qq = unique(t + 1, t + 1 + n) - t - 1;
for (int i = 1; i <= n; i++)
in[i].h = lower_bound(t + 1, t + 1 + qq, in[i].h) - t;
sort(in + 1, in + 1 + n, [](note q, note w) {
if (q.h == w.h)
return q.val < w.val;
return q.h < w.h;
});
for (int i = 1; i <= n; i++)
{
num[in[i].h] += in[i].num;
money[in[i].h] += in[i].num * in[i].val;
t[i] = in[i].val;
}
for (int i = 1; i <= n; i++)
{
money[i] += money[i - 1];
num[i] += num[i - 1];
}
sort(t + 1, t + 1 + n);
qq = unique(t + 1, t + 1 + n) - t - 1;
for (int i = 1; i <= n; i++)
in[i].val = lower_bound(t + 1, t + 1 + qq, in[i].val) - t;
build(1, 200000, 1);
ll ans = 2e18;
for (int i = 1; i <= n; i++)
{
ll res = money[in[n].h] - money[in[i].h];
ll shengyu = num[in[i].h - 1];
ll cnt = max(shengyu - (num[in[i].h] - num[in[i].h - 1] - 1), 0LL);//取的个数
if (in[i].h != in[i - 1].h)
{
val = cnt;
res += query(1, 200000, 1, val);
ans = min(ans, res);
}
ql = qr = in[i].val;
val = i;
update(1, 200000, 1);
}
printf("%lld\n", ans);
}
} D、Number
签到
#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
const int MAXN = 50005;
char s[100005];
int get(int n)
{
int cnt = 0;
while (n)
{
n /= 10;
cnt++;
}
return cnt;
}
int main()
{
{
int n, m;
scanf("%d%d", &n, &m);
int cnt = get(m);
if (n >= cnt)
{
printf("%d", m);
for (int i = 0; i < n - cnt; i++)
printf("0");
printf("\n");
}
else
{
printf("T_T\n");
}
}
} E、find the median
权值线段树维护区间个数，然后加上诡异的离散化。
https://blog.csdn.net/qq_41608020/article/details/99187576
H、Pair
题意:给出三个数字A B C 在1-A中任取一个数字x 在1-B中任取一个数字y 求至少满足 x&y > c 或者 x^y < c其中一个的(x,y)的对数
做法: 数位DP
#include<bits/stdc++.h>
using namespace std;
#define ll long long
/* pos x - limit1 y - limit x&y - limit x^y - limit x - 0 y - 0*/
ll dp[31][2][2][2][2][2][2][2][2];
int a[31], b[31], c[31];
/* limitc1表示 x&y是否等于c ismax1表示x&y是否小于c limitc2 表示 x^y是否等于 c ismax2表示x^y是否大于c*/
ll dfs(int pos, int limitx, int limity, int limitc1, int ismax1, int limitc2, int ismax2, int zero1, int zero2)
{
if (pos == -1)
{
if ((limitc1 == 0 && ismax1 == 0) || (limitc2 == 0 && ismax2 == 0) && zero1 == 0 && zero2 == 0)
return 1ll;
return 0;
}
if (dp[pos][limitx][limity][limitc1][ismax1][limitc2][ismax2][zero1][zero2] != -1)
return dp[pos][limitx][limity][limitc1][ismax1][limitc2][ismax2][zero1][zero2];
ll ans = 0;
int mx = limitx ? a[pos] : 1;
int my = limity ? b[pos] : 1;
for (int i = 0; i <= mx; i++)
{
for (int j = 0; j <= my; j++)
{
int t1 = ismax1, t2 = ismax2;
if (limitc1 == 1 && (i & j) < c[pos])
t1 = 1;
if (limitc2 == 1 && (i ^ j) > c[pos])
t2 = 1;
ans += dfs(pos - 1, limitx && i == mx, limity && j == my, limitc1 && (i & j) == c[pos], t1, limitc2 && (i ^ j) == c[pos], t2, zero1 && i == 0, zero2 && j == 0);
}
}
return dp[pos][limitx][limity][limitc1][ismax1][limitc2][ismax2][zero1][zero2] = ans;
}
int main()
{
int T;
scanf("%d", &T);
while (T--)
{
memset(dp, -1, sizeof(dp));
int A, B, C;
scanf("%d %d %d", &A, &B, &C);
for (int i = 0; i <= 30; i++)
{
if (A & (1 << i))
a[i] = 1;
else
a[i] = 0;
if (B & (1 << i))
b[i] = 1;
else
b[i] = 0;
if (C & (1 << i))
c[i] = 1;
else
c[i] = 0;
}
ll t3 = dfs(30, 1, 1, 1, 0, 1, 0, 1, 1);
printf("%lld\n", t3);
}
} J、A+B problem
签到
#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
const int MAXN = 50005;
int main()
{
int T;
sc("%d", &T);
while (T--)
{
ll a, b;
scanf("%lld%lld", &a, &b);
ll q = 0, w = 0;
while (a)
{
q = q * 10 + a % 10;
a /= 10;
}
while (b)
{
w = w * 10 + b % 10;
b /= 10;
}
ll ans = q + w;
ll ans2 = 0;
while (ans)
{
ans2 = ans2 * 10 + ans % 10;
ans /= 10;
}
printf("%lld\n", ans2);
}
}
360集团公司福利 200人发布