2020 CCPC河南省赛
A - 班委竞选
签到不多说
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
vector<pair<int,int>>v[N];
bool cmp(pair<int,int>a,pair<int,int>b){
if(a.first == b.first)
return a.second < b.second;
return a.first > b.first;
}
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
int n,m; cin>>n>>m;
set<int>s;
for(int i = 1;i <= n; i++)
{
int c,t;
cin>>c>>t;
s.insert(c);
v[c].push_back({t,i});
}
for(auto i : s)
{
sort(v[i].begin(),v[i].end(),cmp);
cout<<v[i][0].second<<" ";
}
return 0;
}
B. 广告投放
很容易想到是DP，但是发现复杂度太高了，怎么办呢？
首先我们定义\(dp[i][j]\)为前\(i\)集，有\(j\)个人时候的最大收益。
如果在第\(i\)集投放广告，那么第\(i+1\)集的收益：\(dp[i+1][j/d[i]]= max(dp[i+1][j/d[i]],dp[i][j]+j*p[i])\)
如果在第\(i\)集不投放广告，那么第\(i+1\)集的收益：\(dp[i+1][j] = max(dp[i+1][j],dp[i][j])\)
这样看起来就像是一个由\(j/d[i]\)转移的背包了。
我们观察一下，第\(i+1\)层都是由第\(i\)层，即它的上一层得到的，我们可以考虑滚动数组来减少一维。考虑完MLE的问题我们要考虑TLE的问题了。同时枚举完所有的\(i,j\)肯定是时间复杂度爆炸的。但是我们知道是由\(j/d[i]\)转移的。意味着，假设\(m\)能转移，但是\(m-1,m-2\)这些是不能的，因为下一个也是\(m/2，m/3\)这些，中间很多是没有意义的。而\(j\rightarrow \lfloor j/d[i]\rfloor\rightarrow \lfloor \lfloor j/d[i]\rfloor/d[i+1] \rfloor=\lfloor j/(d[i]*d[i+1])\rfloor\)。我们可以先预处理出第二维\(j\)的所有可能取值\(\lfloor m/i\rfloor\)(\(i\in[1,m]\))，而\(\lfloor m/i\rfloor\)只有\(\sqrt{m}\)种。
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
ll p[N],d[N],dp[N];
map<ll,ll>mp;
ll n,m,a[N];
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
cin>>n>>m;
for(int i = 1;i <= n; i++)
cin>>p[i];
for(int i = 1;i <= n; i++)
cin>>d[i];
int idx = 0;
a[++idx] = 0;
for(int i = m;i >= 1;i--)
{
if(!mp[m/i])
{
mp[m/i]++;
a[++idx] = m/i;
}
}
for(int i = 1;i <= n; i++)
{
for(int j = 1;j <= idx; j++)
{
dp[a[j]/d[i]] = max(dp[a[j]] + a[j]*p[i],dp[a[j]/d[i]]);
}
}
ll ans = -1e9;
for(int i = 0;i <= m; i++)
ans = max(ans,dp[i]);
cout<<ans<<"\n";
return 0;
}
C - 我得重新集结部队
这个读懂题就很容易啦，是个小模拟。
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
int n;
ll dist(ll x1,ll y1,ll x2,ll y2){
return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
}
bool f[N];
vector<array<ll,4>>c;
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
cin>>n;
memset(f,true,sizeof(f));
for(int i = 1;i <= n; i++)
{
int op; cin>>op;
if(op == 1)
{
ll x,y,h; cin>>x>>y>>h;
c.push_back({x,y,h,i});
}else{
ll x1,y1,atk,r; cin>>x1>>y1>>atk>>r;
ll mindist = 1e18,idx = -1;
for(int j = 0;j < c.size(); j++){
if(f[c[j][3]] == false)continue;
ll x2 = c[j][0],y2 = c[j][1];
if(dist(x1,y1,x2,y2) < mindist){
idx = j;
mindist = dist(x1,y1,x2,y2);
}
}
if(idx == -1)continue;
ll x2 = c[idx][0],y2 = c[idx][1];
ll h = c[idx][2],evt = c[idx][3];
x1 = x2,y1 = y2;
for(int j = 0;j < c.size(); j++){
if(f[c[j][3]] == false)continue;
ll x2 = c[j][0],y2 = c[j][1];
ll h = c[j][2],evt = c[j][3];
ll d = dist(x1,y1,x2,y2);
if(d <= r*r){
h -= 3 * atk;
if(h > 0){
f[i] = false;
c[j][2] = h;
}
else f[evt] = false;
}
}
}
}
for(int i = 1;i <= n; i++){
if(f[i])
cout<<"Yes\n";
else cout<<"No\n";
}
return 0;
}
E - 发通知 (离散化 + 差分)
题意：学院一共有 n 位学生，用 1, 2, ..., n 编号。每天，学院都会派遣辅导员给学生发送若干通知，以保证各项措施、活动消息得到落实。
现在，学院要求辅导员发送一条关于光盘行动的通知。对于通知信息，同学们的反应往往各不相同，辅导员预测出第$ i$ 号学生收到通知后会产生 \(w_i\) 的愉悦度。此外，辅导员还观察到第 i 号学生会在$ [a_i, b_i] $时间段内实时查阅通知消息，能够收到这段时间内的所有通知；而其他时间将无法收到通知（愉悦度为 0）。
辅导员会选择在某一时刻发布一次通知消息，他希望在至少有 k 名同学收到通知的前提下，使得同学们的总体愉悦度最大。同学们的总体愉悦度是所有同学愉悦度的异或和。请聪明的你帮助辅导员计算最大的总体愉悦度。
思路：关于区间操作，很容易会想到差分和前缀和。但是我们发现\(a_i\)和\(b_i\)都很大呀，但是也没有关系，离散化一下就好了。
对于区间\([l,r]\)，我们在\(d[l]\)+=\(1\),\(d[r+1]\)-=\(1\)。同样的\(t[l]\) ^= \(w\),\(t[r+1]\) ^= \(w\)。
离散化也是常操，unique一下。
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 5e5 + 10;
ll a[N],b[N],w[N];
ll d[N*2],t[N*2];
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
int n,k; cin>>n>>k;
vector<ll>v;
for(int i = 1;i <= n; i++)
{
cin>>a[i]>>b[i]>>w[i];
v.push_back(a[i]);
v.push_back(b[i]+1);
}
sort(v.begin(),v.end());
v.erase(unique(v.begin(),v.end()))-v.end();
for(int i = 1 ; i <= n ; i ++)
{
int l = lower_bound(v.begin(), v.end(), a[i]) - v.begin() + 1;
int r = lower_bound(v.begin(), v.end(), b[i] + 1ll) - v.begin() + 1;
d[l] += 1ll, d[r] -= 1ll;
t[l] ^= w[i], t[r] ^= w[i];
}
ll ans = -1;
int len = v.size();
for(int i = 1 ; i <= len; i ++)
{
d[i] += d[i - 1];
t[i] ^= t[i - 1];
if(d[i] >= k)
ans = max(ans,t[i]);
}
cout<<ans<<"\n";
return 0;
}
当然你愿意用map也是可以的，但是常数比较大
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
map<int,pair<int,int>>mp;
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
int n,k; cin>>n>>k;
for(int i = 1;i <= n; i++)
{
int a,b,w; cin>>a>>b>>w;
mp[a].first ^= w;
mp[a].second += 1;
mp[b+1].first ^= w;
mp[b+1].second -= 1;
}
int hav = 0;
int ans = -1,now = 0;
for(auto x : mp){
now ^= x.second.first;
hav += x.second.second;
if(hav >= k)
ans = max(ans,now);
}
cout<<ans<<"\n";
return 0;
}
ps:布吉岛为什么，那么容易的我写了辣么久emmm，果然是太久没写啦。
I. 太阳轰炸
思路：这个题其实很简单。分情况讨论。
if(a*n < h ),即所有都命中还是不能，答案就是0
else if(\(R_1+r \ge R_2\))那么每次都能命中，答案是1
else{
有概率命中，有概率不命中，我们要算出概率。
\(R_3 = R_1+r\)，在\(\le R_3\)可以命中。
命中的概率：\(p_1 = \dfrac{\pi R_3^2}{\pi R_2^2}=\dfrac{R_3^2}{R_2^2}\)
未命中的概率\(p_2 = 1-p_1 = \dfrac{R_2^2-R_3^2}{R_2^2}\)
接着算出至少需要命中的次数\(need = h/a + (h\%a!=0)\)。那么命中\(\ge need\)都是可以的。
\(ans = \sum_{i = need}^{n}C_n^ip_1^ip_2^{n-i}\)
}
可以\(O(n)\)预处理出组合数和次幂。
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 5e6 + 10;
ll fac[N],inv[N];
ll qmi(ll a, ll b, ll mod)
{
ll ans = 1 % mod;
while(b)
{
if(b & 1) ans = ans * a % mod;
a = a * a % mod;
b >>= 1;
}
return ans;
}
ll C(ll a,ll b)
{
return fac[a]*inv[b]%mod*inv[a-b]%mod;
}
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
ll n,R1,R2,r,a,h; cin>>n>>R1>>R2>>r>>a>>h;
if(n*a < h)
{
cout<<0<<"\n";
return 0;
}
if(R2 <= R1+r){
cout<<1<<"\n";
}
else
{
fac[0]=1;
for(int i=1;i<=n+1;i++) fac[i]=fac[i-1]*i%mod;//预处理出阶乘、阶乘的逆元
inv[n+1]=qmi(fac[n+1],mod-2,mod);
for(int i=n;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;
ll R3 = (R1+r)%mod;
ll t = qmi(R2,2,mod);
ll inv2 = qmi(t,mod-2,mod);
ll p1 = R3*R3%mod*inv2%mod;
ll p2 = ((R2*R2%mod - R3*R3%mod + mod)%mod)*inv2%mod;
if(p2 < 0)
p2 = (p2 + mod)%mod;
ll need = (h/a + (h % a != 0))%mod;
ll ans = 0;
for(int i = need;i <= n; i++)
{
ans = (ans + C(n,i)*qmi(p1,i,mod)%mod*qmi(p2,n-i,mod)%mod)%mod;
}
cout<<ans<<"\n";
}
return 0;
}
写法2：
论我一开始为什么T了（悲
每次用快速幂求逆元，组合数也没用\(O(n)\)预处理，每次单独求了(我是在干什么)。
T了之后改改如何过了。
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
ll qmi(ll a, ll b, ll mod)
{
ll ans = 1 % mod;
while(b)
{
if(b & 1) ans = ans * a % mod;
a = a * a % mod;
b >>= 1;
}
return ans;
}
ll C(ll a, ll b, int p)
{
if (b > a) return 0;
ll res = 1;
for (int i = 1, j = a; i <= b; i ++, j -- )
{
res = (ll)res * j % p;
res = (ll)res * qmi(i, p - 2, p) % p;
}
return res;
}
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
ll n,R1,R2,r,a,h; cin>>n>>R1>>R2>>r>>a>>h;
if(n*a < h)
{
cout<<0<<"\n";
return 0;
}
if(R2<=R1+r)
cout<<1<<"\n";
else
{
ll R3 = (R1+r)%mod;
ll t = qmi(R2,2,mod);
ll inv = qmi(t,mod-2,mod);
ll p1 = (((R3*R3)%mod)*inv)%mod;
ll p2 = ((R2*R2%mod - R3*R3%mod + mod)%mod)*inv%mod;
if(p2 < 0)
p2 = (p2 + mod)%mod;
ll need = (h/a + (h % a != 0))%mod;
ll ans = 0;
vector<ll>v,v2;
ll t1 = qmi(p1,need,mod),t2 = 1;
for(int i = need;i <= n; i++){
v.push_back(t1%mod);
t1 = t1*p1%mod;
v2.push_back(t2);
t2 = t2*p2%mod;
}
int l = 0,r = v2.size()-1;
ll fz = 1,fm = 1;
ll x = n,y = need;
for(int i = need;i >=1; i--)
{
fz = fz * x % mod;
fm = fm * y % mod;
x--;
y--;
};
for(ll i = need;i <= n; i++)
{
//ans = (ans + (((fz*qmi(fm,mod-2,mod))%mod*v[l++])%mod*v2[r--])%mod)%mod;
ll t = fz*qmi(fm,mod-2,mod)%mod;
t = t * v[l++] %mod;
t = t * v2[r--] %mod;
ans = (ans + t) % mod;
fz = fz*x%mod;
fm = ((fm*(i+1)%mod)%mod)%mod;
x--;
}
cout<<ans<<"\n";
}
return 0;
}