1．计数
(count.cpp/c/pas)
时间限制：1s
内存限制：256MB
【问题描述】
给出 \(m\) 个数 \(a_1,a_2,…,a_m\)
求 1~n 中有多少数不是 \(a_1,a_2,…,a_m\) 的倍数。
【输入】
输入文件名为 count.in。
第一行，包含两个整数：\(n,m\)
第二行，包含 \(m\) 个数，表示 \(a_1,a_2,…,a_m\)
【输出】
输出文件名为 count.out。
输出一行，包含 \(1\) 个整数，表示答案
【输入输出样例】
count.in
10 2
2 3
count.out
3
【数据说明】
对于 \(60\%\) 的数据，\(1 \le n \le 10^6\)
对于另外 \(20\%\) 的数据，\(m=2\)
对于 \(100\%\) 的数据，\(1 \le n \le 10^9,0 < m \le 20,1 \le a[i] \le 10^9\)
容斥即可。
算出重复的，然后将其减去。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define bug puts("STOP!");
#define rep(i, a, b, c) for (int i = (a); i <= (b); i += (c))
#define per(i, a, b, c) for (int i = (a); i >= (b); i -= (c))
template<typename T>
inline T read() {
T x = 0;
int fg = 0;
char ch = getchar();
while (ch < '0' || ch > '9') {
fg |= (ch == '-');
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + (ch ^ 48);
ch = getchar();
}
return fg ? ~x + 1 : x;
}
const int M = 25;
ll n, m, ans;
ll a[M];
bool vis[M];
ll gcd(ll a, ll b) {
if (!b) {
return a;
}
return gcd(b, a % b);
}
ll lcm(ll a, ll b) {
ll g = gcd(a, b);
return a / g * b;
}
void work() {
int cnt = 0;
ll Lcm = 1;
rep (i, 1, m, 1) {
if (vis[i]) {
Lcm = lcm(Lcm, a[i]);
++ cnt;
}
}
if (cnt == 0) return ;
if (cnt & 1) {
ans += (n / Lcm);
} else {
ans -= (n / Lcm);
}
}
void dfs(int u) {
if (u > m) {
work();
return ;
}
vis[u] = 1;
dfs(u + 1);
vis[u] = 0;
dfs(u + 1);
}
int main() {
freopen("count.in", "r", stdin);
freopen("count.out", "w", stdout);
n = read<int>(), m = read<int>();
rep (i, 1, m, 1) {
a[i] = read<int>();
}
dfs(1);
printf("%lld\n", n - ans);
fclose(stdin);
fclose(stdout);
return 0;
}
2．区间第 k 大
(kth.cpp/c/pas)
时间限制：1s
内存限制：256MB
【问题描述】
一个区间的价值定义为该区间中的最大值减最小值
给定 \(n\) 个数，求所有区间价值中，第 \(k\) 大值为多少。
【输入】
输入文件名为 kth.in。
第 \(1\) 行两个数 \(n\)、\(k\) \(\left (k \le \dfrac{n \times(n-1)}{2} \right )\)
第 \(2\) 行 \(n\) 个数,每个数 \(\le 10^9\)
【输出】
输出文件名为 kth.out。
输出区间价值的第 \(k\) 大值。
【输入输出样例】
| kth.in | kth.out |
|---|---|
| 3 2 2 1 3 |
2 |
【样例解释】
\([l,r]\)表示第 \(l\) 个数到第 \(r\) 个数组成的区间的价值
\([1,1]=0\) \([1,2]=1\) \([1,3]=2\)
\([2,2]=0\) \([2,3]=2\)
\([3,3]=0\)
【数据说明】
对于 \(30\%\) 的数据，\(n=500\)
对于 \(60\%\)的数据，\(n \le 5000\)
对于 \(100\%\) 的数据，\(n \le 400000\)
ST 表 + 堆 即可得到 \(60\) 分的好成绩。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define bug puts("STOP!");
#define rep(i, a, b, c) for (int i = (a); i <= (b); i += (c))
#define per(i, a, b, c) for (int i = (a); i >= (b); i -= (c))
template<typename T>
inline T read() {
T x = 0;
int fg = 0;
char ch = getchar();
while (ch < '0' || ch > '9') {
fg |= (ch == '-');
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + (ch ^ 48);
ch = getchar();
}
return fg ? ~x + 1 : x;
}
const int N = 4e5 + 5;
int n, k;
int a[N], lg[N];
int st[N][20][2];
priority_queue<int, vector<int>, greater<int> > q;
inline int query(int l, int r, int op) {
int k = lg[r - l + 1];
if (op == 1) {
return max(st[l][k][1], st[r - (1 << k) + 1][k][1]);
} else {
return min(st[l][k][0], st[r - (1 << k) + 1][k][0]);
}
}
int main() {
freopen("kth.in", "r", stdin);
freopen("kth.out", "w", stdout);
n = read<int>(), k = read<int>();
lg[0] = -1;
rep (i, 1, n, 1) {
lg[i] = lg[i >> 1] + 1;
a[i] = read<int>();
st[i][0][0] = st[i][0][1] = a[i];
}
rep (j, 1, 19, 1) {
rep (i, 1, n, 1) {
if (i + (1 << j) - 1 > n) break ;
st[i][j][1] = max(st[i][j - 1][1], st[i + (1 << (j - 1))][j - 1][1]);
st[i][j][0] = min(st[i][j - 1][0], st[i + (1 << (j - 1))][j - 1][0]);
}
}
rep (len, 1, n, 1) {
rep (i, 1, n - len + 1, 1) {
int maxx = query(i, i + len - 1, 1), minn = query(i, i + len - 1, 0);
int ans = maxx - minn;
if ((int)q.size() < k) {
q.emplace(ans);
} else {
if (q.top() < ans) {
q.pop();
q.emplace(ans);
}
}
}
}
printf("%d\n", q.top());
return 0;
}
正解：二分答案
二分答案 \(ans\)，统计有多少个区间的价值大于等于 \(ans\)
区间 \([l-1,r]\) 的价值一定大于等于 \([l,r]\)，所以对于每一右端点 \(i\)， 必定存在一个阀值 \(K_i\) 使得对于所有的 \(l \le K_i [l,i]\) 的价值必定大于等于 \(ans\)
且随之 \(i\) 的增大，\(K_i\) 也必定单调不降
用两个单调队列来维护阀值 \(K\) 的移动（ 一个维护最小值， 一个维护最大值， 当 \(K\) 增加时判定最大值－ 最小值是否大于等于 \(ans\) 即可）
时间复杂度 \(O(\log_{2}(10^9) \cdot n)\)
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pr;
const double pi=acos(-1);
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,n,a) for(int i=n;i>=a;i--)
#define Rep(i,u) for(int i=head[u];i;i=Next[i])
#define clr(a) memset(a,0,sizeof a)
#define pb push_back
#define mp make_pair
#define putk() putchar(' ')
ld eps=1e-9;
ll pp=1000000007;
ll mo(ll a,ll pp){if(a>=0 && a<pp)return a;a%=pp;if(a<0)a+=pp;return a;}
ll powmod(ll a,ll b,ll pp){ll ans=1;for(;b;b>>=1,a=mo(a*a,pp))if(b&1)ans=mo(ans*a,pp);return ans;}
ll gcd(ll a,ll b){return (!b)?a:gcd(b,a%b);}
ll read(){
ll ans=0;
char last=' ',ch=getchar();
while(ch<'0' || ch>'9')last=ch,ch=getchar();
while(ch>='0' && ch<='9')ans=ans*10+ch-'0',ch=getchar();
if(last=='-')ans=-ans;
return ans;
}
void put(ll a){
if(a<0)putchar('-'),a=-a;
int top=0,q[20];
while(a)q[++top]=a%10,a/=10;
top=max(top,1);
while(top--)putchar('0'+q[top+1]);
}
//head
#define N 410000
int a[N],q1[N],q2[N];
ll k;
int n;
bool check(int kk){
int l1=1,r1=1,l2=1,r2=1;
q1[1]=1;q2[1]=1;
int z=1;
ll ans=0;
if(kk==1)ans=1;
else ans=0;
rep(i,2,n){
while(l1<=r1 && a[q1[r1]]>=a[i])--r1;
q1[++r1]=i;
while(l2<=r2 && a[q2[r2]]<=a[i])--r2;
q2[++r2]=i;
while(z<i){
int t1=l1,t2=l2;
++z;
while(q1[t1]<z)++t1;
while(q2[t2]<z)++t2;
if(a[q2[t2]]-a[q1[t1]]>=kk){
l1=t1;
l2=t2;
}
else{
--z;
break;
}
}
if(a[q2[l2]]-a[q1[l1]]>=kk)ans+=z;
}
return ans>=k;
}
int main(){
freopen("kth.in","r",stdin);
freopen("kth.out","w",stdout);
n=read();k=read();
rep(i,1,n)a[i]=read();
int l=0,r=1000000000;
while(l<r){
int mid=(l+r+1)/2;
if(check(mid))l=mid;
else r=mid-1;
}
cout<<l<<endl;
return 0;
return 0;
}
3．武器分配
(submax.cpp/c/pas)
时间限制：1s
内存限制：256MB
【问题描述】
有 \(n\) 个堡垒排成一排构成了一条防御线。现在需要将 \(n\) 个武器放入这 \(n\) 个堡垒中，每个堡垒放一个，每个武器有攻击力和战场贡献值两个属性。
由于这 \(n\) 个武器都不是人为操控的，所以会对其某半径内所有单位进行攻击，而这就导致某些堡垒的互相攻击。现在发现第 \(i\) 个堡垒会和第 \(j\) 个堡垒互相攻击当且仅当 \(|i-j| \le r\)，且攻击力较低的武器和他所在的堡垒会破损。
现在你需要给出一种武器分配方案使得未破损武器的战场贡献值总和最大。为了方便你只需输出战场贡献值总和的最大值即可。
【输入】
输入文件名为 submax.in。
第一行一个数 \(T(T \le 10)\)，表示数据组数
对于每一组数据：
第一行两个数 \(n\)，\(r\)
第二行 \(n\) 个数，表示 \(1 \sim n\) 号武器的攻击力
第三行 \(n\) 个数，表示 \(1 \sim n\) 号武器的战场贡献值
【输出】
输出文件名为 submax.out。
对于每组数据输出一个数，表示答案
【输入输出样例】
| submax.in | submax.out |
|---|---|
| 1 4 2 1 2 3 4 1 2 3 4 |
7 |
【数据范围】
对于 \(30\%\) 的数据：\(n \le 10\)
对于 \(50\%\) 的数据，\(n \le 16\)
对于 \(100\%\) 的数据 ， \(n \le 5000\),武器攻击力 \(\le 100000\) 且两两不同 ，武器的战场贡献值 \(\le 100000,r<n.\)
\(n!\) 的枚举有 \(30\) 分。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define bug puts("STOP!");
#define rep(i, a, b, c) for (int i = (a); i <= (b); i += (c))
#define per(i, a, b, c) for (int i = (a); i >= (b); i -= (c))
template<typename T>
inline T read() {
T x = 0;
int fg = 0;
char ch = getchar();
while (ch < '0' || ch > '9') {
fg |= (ch == '-');
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + (ch ^ 48);
ch = getchar();
}
return fg ? ~x + 1 : x;
}
const int N = 5010;
int n, r, T;
ll res, ans;
int attack[N], v[N], idn[N];
bool vis[N], damage[N];
void work() {
res = 0;
rep (i, 1, n, 1) {
damage[i] = 0;
}
rep (i, 1, n, 1) {
rep (j, max(0, i - r), min(n, i + r), 1) {
if (attack[idn[j]] < attack[idn[i]]) {
damage[idn[j]] = 1;
}
}
}
rep (i, 1, n, 1) {
if (!damage[i]) {
res += v[i];
}
}
ans = max(ans, res);
}
void dfs(int u) {
if (u > n) {
work();
return ;
}
rep (i, 1, n, 1) {
if (vis[i]) continue ;
vis[i] = 1;
idn[u] = i;
dfs(u + 1);
vis[i] = 0;
idn[u] = 0;
}
}
void solve() {
ans = 0;
n = read<int>(), r = read<int>();
rep (i, 1, n, 1) {
attack[i] = read<int>();
idn[i] = 0;
vis[i] = 0;
}
rep (i, 1, n, 1) {
v[i] = read<int>();
}
dfs(1);
printf("%lld\n", ans);
}
int main() {
freopen("submax.in", "r", stdin);
freopen("submax.out", "w", stdout);
T = read<int>();
while (T --) {
solve();
}
return 0;
}
正解：区间 DP。
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<ctime>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pr;
const double pi=acos(-1);
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,n,a) for(int i=n;i>=a;i--)
#define Rep(i,u) for(int i=head[u];i;i=Next[i])
#define clr(a) memset(a,0,sizeof a)
#define pb push_back
#define mp make_pair
#define INF 1000000000
ld eps=1e-9;
ll pp=1000000007;
ll mo(ll a,ll pp){if(a>=0 && a<pp)return a;a%=pp;if(a<0)a+=pp;return a;}
ll powmod(ll a,ll b,ll pp){ll ans=1;for(;b;b>>=1,a=mo(a*a,pp))if(b&1)ans=mo(ans*a,pp);return ans;}
ll read(){
ll ans=0;
char last=' ',ch=getchar();
while(ch<'0' || ch>'9')last=ch,ch=getchar();
while(ch>='0' && ch<='9')ans=ans*10+ch-'0',ch=getchar();
if(last=='-')ans=-ans;
return ans;
}
void put(ll n){
int top=0;int qq[22];
while(n)qq[++top]=n%10,n/=10;
if(top==0)top=1,qq[0]=0;
while(top)putchar('0'+qq[top]),top--;
}
//head
#define N 5100
int dp[N/2][N],n,r;
struct node{
int x,y;
}q[N];
bool cmp(node a,node b){
return a.x<b.x;
}
void solved(){
n=read();r=read();
rep(i,1,n)q[i].x=read();
rep(i,1,n)q[i].y=read();
sort(q+1,q+n+1,cmp);
int m=n/(1+r)+((n%(1+r))>0);
int ans=0;
rep(i,1,m){
int tt=min((1+r)*i,n);
rep(j,0,tt-1)dp[i][j]=-INF;
rep(j,tt,n)dp[i][j]=q[j].y+dp[i-1][j-1];
rep(j,1,n)dp[i][j]=max(dp[i][j],dp[i][j-1]);
ans=max(ans,dp[i][n]);
}
printf("%d\n",ans);
}
int main(){
freopen("submax.in","r",stdin);
freopen("submax.out","w",stdout);
int T=read();
while(T--)solved();
return 0;
}