第一次:排名出来了,27名,离进队还差一点,要继续努力!
7.22场链接
A题:
题意:一共有n张牌,每张牌有一个属性值(a,b,c),每次比大小之前可以任意调换三个属性的位置,求有多少张牌通过这种方式肯定能战胜其他的牌。
解法:首先我们找出每张牌的属性值的最小的两个的最大值,之后我们依次枚举每个牌,看这张牌上最大的两个属性的牌能不能大于那最小的属性值,如果可以的话,这张牌就可以,符合要求。
#include<cstdio>
#include<iostream>
#include<set>
#include<algorithm>
using namespace std;
typedef set<int>::iterator si;
const int maxn = 2e5 + 5;
struct poker {
int a, b, c;
//poker(int aa, int bb, int cc): a(aa), b(bb), c(cc) {}
bool operator < (const poker & rhs) {
return (a < rhs.a&&b < rhs.b) || (a < rhs.a&&c < rhs.c) || (b < rhs.b&&c < rhs.c)
|| (a < rhs.a&&b < rhs.b&&c < rhs.c);
}
};
poker p[maxn];
int main() {
int n; scanf("%d", &n);
int min1, min2;
for (int i = 0; i < n; i++) {
int a[3];
scanf("%d%d%d", &a[0], &a[1], &a[2]);
sort(a, a + 3);
p[i] = poker{ a[0], a[1], a[2] };
min1 = max(min1, a[0]); min2 = max(min2, a[1]);
}
int ans = 0;
for (int i = 0; i < n; i++) {
if (p[i].c > min2&&p[i].b > min1)ans++;
}
printf("%d
", ans);
return 0;
}
B题:
题意:设 f(n) 表示 n 的每一位数字的平方之和,求 [a,b] 中有几个 n 满足 k × f(n)=n
解法:不是数位dp。由于最多18位,所以f(i)情况数最多为1458。我们依次枚举所有的这些情况,也就是每枚举一位,就根据公式算出来n的值,再对n分解因式,求每一位的平方和,之后判断这个平方和与枚举的f(i)是否一样,进而判断。
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
int main() {
ll k, l, r;
scanf("%lld%lld%lld", &k, &l, &r);
ll side = min(1ll*1458, r / k), ans = 0;
for (int i = 1; i <= side; i++) {
ll n = k*i, res=0;
if (n<l || n>r)continue;
while (n) { res += (n % 10)*(n % 10); n /= 1LL*10; }
if (res == i)ans++;
}
printf("%lld", ans);
return 0;
}
C题:
题意:小 Hi 手上有 n 张面值互不相同的钱币,且面值都是 2 的幂次,现在他想知道,他可以组合出多少种小于等于 c 的正整数金额。
解法:这道题比较复杂,又是一道二进制的经典例题
首先我们算出来一共有多少种钱币,之后分离出来c的每一位,如果这一位是1而且这一位的N_bit[]不为0,就往下拓展
这道题没怎么弄懂,以后要多看
//雷大佬牛批!
#include<cstdio>
using namespace std;
typedef long long ll;
ll pow[100];
int N_bit[100], C_bit[100], sum[100];
int main() {
int n;
ll c;
scanf("%d%lld", &n, &c);
pow[0] = 1;
//pow[i]是2的i次方
for (int i = 1; i <= 63; i++) {
pow[i] = pow[i - 1] * 2;
}
//N_bit[i]表示面值为2的i次方的硬币有多少个
for (int i = 1; i <= n; i++) {
ll tmp;
scanf("%lld", &tmp);
int t = -1;
while (tmp) {
++t;
tmp >>= 1;
}
N_bit[t] += 1;
}
//sum[i]表示2的i次方以前的硬币共有多少种
sum[0] = N_bit[0];
for (int i = 1; i <= 64; i++) {
sum[i] = sum[i - 1] + N_bit[i];
}
//分离要求的c的每一位
ll tmp = c;
int t = 0;
while (tmp) {
C_bit[t] = (tmp & 1);
tmp >>= 1;
t++;
}
t--;
//从高到低枚举每一位,每一位的方案总数为小于它的钱币个数(拿或不拿)
ll ans = 0;
for (int i = t; i >= 0; i--) {
if (C_bit[i]) {
ans += pow[sum[i - 1]];
if (!N_bit[i])break;
}
}
printf("%lld
", ans - 1);
return 0;
}
E题:(莫队)
题意:有一个序列,长度为n,定义这段序列的权值为这段序列所有数组的(Ks·Ks·s)之和 ,Ks为s在这段序列中出现的次数,给出m个区间,问每个区间的权值为多少。
解法:莫队求解,模板题
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 1e6 + 5;
typedef long long ll;
int pos[maxn], vis[maxn * 10], a[maxn];
ll ans[maxn], num;
struct node {
int l, r, id;
node(){}
node(int l, int r, int id) :l(l), r(r), id(id) {}
bool operator < (const node& rhs) {
return pos[l] < pos[rhs.l] || (pos[l] == pos[rhs.l] && pos[r] < pos[rhs.r]);
}
};
node q[maxn];
void add(int x) {
vis[x]++;
num += x*(vis[x] * vis[x] - (vis[x] - 1)*(vis[x] - 1));
}
void del(int x) {
vis[x]--;//vis[x]已经减过了
num -= x*((vis[x] + 1)*(vis[x] + 1) - vis[x] * vis[x]);
}
int main() {
int n, m;
scanf("%d%d", &n, &m);
ll len = sqrt(1.0*n);
for (int i = 1; i <= n; i++){
scanf("%d", &a[i]);
pos[i] = i / len;
}
for (int i = 1; i <= m; i++){
scanf("%d %d", &q[i].l, &q[i].r);
q[i].id = i;
}
sort(q + 1, q + 1 + m);
num = 0;
int l = 1, r = 0;
for (int i = 1; i <= m; i++)
{
while (r < q[i].r) add(a[++r]);
while (r > q[i].r) del(a[r--]);
while (l < q[i].l) del(a[l++]);
while (l > q[i].l) add(a[--l]);
ans[q[i].id] = num;
}
for (int i = 1; i <= m; i++)
printf("%I64d
", ans[i]);
return 0;
}
Uva1608
题意:如果一个序列的任意连续子序列中至少有一个只出现了一次的元素,则称这个序列是non-boring。输入n个元素的序列,判断它是不是无聊的。
解法:枚举区间
#include<cstdio>
#include<iostream>
#include<map>
#include<set>
using namespace std;
const int maxn = 2e5 + 5;
int a[maxn], pre[maxn], nex[maxn];
map<int, int>mp;
int n;
//pre[i]是左边离他最近的元素的下标,nex[i]是右边离他最近的元素的下标
//枚举区间,如果a[i]是这个区间内唯一出现的元素,那么我们只去要判断l~i-1
//以及i+1~r即可
int check(int l, int r) {
if (l >= r)return 1;
for (int i = l, j = r; i <= j; i++, j--) {
if (pre[i]<l&&nex[i]>r)return check(l, i - 1) && check(i + 1, r);
if (pre[j]<l&&nex[j]>r)return check(l, j - 1) && check(j + 1, r);
}
return 0;
}
int main() {
int T; scanf("%d", &T);
while (T--) {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
mp.clear();
for (int i = 1; i <= n; i++) {
if (mp.count(a[i])) pre[i] = mp[a[i]];
else pre[i] = -1;
mp[a[i]] = i;
}
mp.clear();
for (int i = n ; i >= 1; i--) {
if (mp.count(a[i])) nex[i] = mp[a[i]];
else nex[i] = n+1;
mp[a[i]] = i;
}
if (check(1, n))printf("non-boring
");
else printf("boring
");
}
return 0;
}