2018 China Collegiate Programming Contest Final
A Mischievous Problem Setter
题目链接
题意：n道题，每道题具有难度和时间，按照难度解题，求m分钟解题数量
思路：按顺序计算总和即可
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 1e5 + 5;
const int inf = 0x3f3f3f3f;
struct node {
int D, T;
}k[maxn];
int main() {
int t;
scanf("%d", &t);
int ca = 0;
while (t--) {
printf("Case %d: ", ++ca);
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%d", &k[i].D);
}
for (int i = 1; i <= n; i++) {
scanf("%d", &k[i].T);
}
sort(k + 1, k + 1 + n, [&](node a, node b) {
return a.D < b.D;
});
int cnt = 0;
for (int i = 1; i <= n; i++) {
//cout << k[i].D << endl;
if (m >= k[i].T) {
m -= k[i].T;
cnt++;
}
else {
break;
}
}
cout << cnt << endl;
}
}
/*
2
5 120
5 10 20 35 100
10 20 35 100 100000
13 300
52 55 82 11 62 79 38 8 58 28 1 70 32
27 62 45 77 22 69 34 43 21 43 85 22 36
*/ B Balance of the Force
题目链接
题意：每个人都可以分属为光明或黑暗阵营，对其阵营产生ai和bi的贡献值，要求每个人分属完后的max贡献-min贡献最小。人与人之间有厌恶关系，即两个人厌恶就不能在同一阵营。
思路：通过种类并查集或者DFS染色来区分不同阵营的人。可以形成若干个集合，记录集合最大和最小值，对于一个集合，其存在光明和黑暗两种可能，排序后遍历一维，用线段树记录另一维的最值，当两个集合属于同一个并查集就覆盖取最优情况。
#include <bits/stdc++.h>
#define maxn 200005
#define inf 0x3f3f3f3f
using namespace std;
int n,m;
int cnt,tot;
int flag=0;
int fa[maxn];
int value[maxn];
int vis[maxn];
int in_maxx[maxn];
int in_tree[maxn];
int find(int x){
if(x!=fa[x]){
int t=fa[x];
fa[x]=find(fa[x]);
value[x]=(value[x]+value[t])%2;
}
return fa[x];
}
void mix(int x,int y,int s){
int fx=find(x);
int fy=find(y);
if(fx!=fy){
fa[fx]=fy;
value[fx]=value[x]^value[y]^s;
}else if(value[x]==value[y]){
flag=1;
}
}
void init(){
flag=0;
cnt=0;
tot=0;
for(int i=1;i<=n;i++){
fa[i]=i;
value[i]=0;
vis[i]=0;
}
}
struct point{
int x,y;
}a[maxn];
struct node{
int maxx,minn;
int id;
node(int a=inf,int b=-inf,int c=0):minn(a),maxx(b),id(c){}
}t[maxn<<1];
bool cmp(node a,node b){
if(a.minn==b.minn)
return a.maxx<b.maxx;
return a.minn>b.minn;
}
int tree[maxn<<2];
void Build(int l,int r,int rt){
tree[rt]=-inf;
if(l==r)return;
int mid=(l+r)>>1;
Build(l,mid,rt<<1);
Build(mid+1,r,rt<<1|1);
}
void pushup(int rt){
tree[rt]=max(tree[rt<<1],tree[rt<<1|1]);
}
void update(int index,int x,int l,int r,int rt){
if(l==r){
tree[rt]=x;
return;
}
int mid=(l+r)>>1;
if(index<=mid)
update(index,x,l,mid,rt<<1);
else
update(index,x,mid+1,r,rt<<1|1);
pushup(rt);
}
int main(){
int T;
scanf("%d",&T);
for(int cas=1;cas<=T;cas++){
scanf("%d%d",&n,&m);
init();
int u,v;
for(int i=1;i<=m;i++){
scanf("%d%d",&u,&v);
mix(u,v,1);
}
for(int i=1;i<=n;i++){
scanf("%d%d",&a[i].x,&a[i].y);
if(flag)continue;
u=find(i);
if(!vis[u]){
cnt+=2;
vis[u]=cnt-1;
if(!value[i]){
t[cnt-1]=node(a[i].x,a[i].x,++tot);
t[cnt]=node(a[i].y,a[i].y,tot);
}else{
t[cnt-1]=node(a[i].y,a[i].y,++tot);
t[cnt]=node(a[i].x,a[i].x,tot);
}
in_tree[tot]=0;
}else{
if(!value[i]){
t[vis[u]].minn=min(t[vis[u]].minn,a[i].x);
t[vis[u]].maxx=max(t[vis[u]].maxx,a[i].x);
t[vis[u]+1].minn=min(t[vis[u]+1].minn,a[i].y);
t[vis[u]+1].maxx=max(t[vis[u]+1].maxx,a[i].y);
}else{
t[vis[u]].minn=min(t[vis[u]].minn,a[i].y);
t[vis[u]].maxx=max(t[vis[u]].maxx,a[i].y);
t[vis[u]+1].minn=min(t[vis[u]+1].minn,a[i].x);
t[vis[u]+1].maxx=max(t[vis[u]+1].maxx,a[i].x);
}
}
}
printf("Case %d: ",cas);
if(flag){
printf("IMPOSSIBLE\n");
continue;
}
Build(1,tot,1);
sort(t+1,t+cnt+1,cmp);
int sum=0,id=0,ans=inf;
for(int i=1;i<=cnt;i++){
// cout<<t[i].minn<<' '<<t[i].maxx<<endl;
if(sum==tot){
if(t[i].maxx<t[in_maxx[t[i].id]].maxx)
update(in_tree[t[i].id],t[i].maxx,1,tot,1);
ans=min(ans,tree[1]-t[i].minn);
}else{
if(!in_tree[t[i].id]){
sum++;
in_tree[t[i].id]=++id;
in_maxx[t[i].id]=i;
update(id,t[i].maxx,1,tot,1);
if(sum == tot) ans = min(ans, tree[1] - t[i].minn);
}else if(t[i].maxx<t[in_maxx[t[i].id]].maxx)
update(in_tree[t[i].id],t[i].maxx,1,tot,1);
}
}
printf("%d\n",ans);
}
} G Pastoral Life in Stardew Valley
题目链接
题意：在 n×m 的棋盘上选择两个长方形使一个长方形完全包含另一个长方形，求方案数
思路：
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll maxn = 1e5 + 5;
const ll inf = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
ll x3[maxn], x2[maxn], x1[maxn];
void init() {
x3[0] = 0;
x2[0] = 0;
x1[0] = 0;
for (ll i = 1; i < maxn; i++) {
x3[i] = (x3[i - 1] + i * i*i%mod) % mod;
x2[i] = (x2[i - 1] + i * i%mod) % mod;
x1[i] = (x1[i - 1] + i % mod) % mod;
// cout << i << " " << x3[i] << " " << x2[i] << " " << x1[i] << endl;
}
}
ll qpow(ll A, ll B) {
ll t = 1;
while (B) {
if ((B & 1)) {
t = t * A%mod;
}
A = A * A%mod;
B = B >> 1;
}
return t;
}
ll fun(ll n) {
ll res = (((mod - x3[n - 2] % mod) % mod + (n - 2)*x2[n - 2] % mod + ((n - 1)*x1[n - 2] % mod) % mod)) % mod;
// printf("*%d ", res);
res = res * qpow(2ll, mod - 2) % mod;
return res;
}
int main() {
init();
ll t;
scanf("%lld", &t);
int ca = 0;
while (t--) {
printf("Case %d: ", ++ca);
ll n, m;
scanf("%lld%lld", &n, &m);
if (n <= 2 || m <= 2)puts("0");
else printf("%lld\n", fun(n)*fun(m)%mod);
}
} I Cockroaches
题目链接
题意：二维平面上有若干只蟑螂，一种工具可以对一个点释放，使同一行和同一列蟑螂都死掉，求最多杀死蟑螂数和方案数。
思路：先求出最多的蟑螂数量，然后通过已知最多的蟑螂数量推出相对应多少中方案数。
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll maxn = 1e5 + 5;
const ll inf = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
struct Hash {
ll a[maxn], cnt;
void init() { cnt = 0; }
void add(ll x) { a[++cnt] = x; }
void work() {
sort(a + 1, a + 1 + cnt);
cnt = unique(a + 1, a + 1 + cnt) - a - 1;
}
ll get(ll x) {
return lower_bound(a + 1, a + 1 + cnt, x) - a;
}
}hsx,hsy;
ll x[maxn], y[maxn];
ll numx[maxn], numy[maxn];
vector<ll>v[maxn];
ll fun_ans() {
ll ma = 0;
ll cnt = 0;
for (ll i = 1; i <= hsx.cnt; i++) {
if (ma > numx[i]) {
continue;
}
else if (ma == numx[i]) {
cnt++;
}
else{
ma = numx[i];
cnt = 1;
}
}
//cout << ma << "**" << cnt << endl;
ll res = 0;
for (ll i = 1; i <= hsy.cnt; i++) {
ll resy = numy[i];
ll ct = 0;
for (ll j : v[i]) {
if (numx[j] == ma) {
ct++;
}
}
if (ct == cnt) {
res = max(res, ma + numy[i] - 1);
}
else {
res = max(res, ma + numy[i]);
}
}
ll second_cnt = 0;
for (ll i = 1; i <= hsx.cnt; i++) {
if (numx[i] == ma - 1) {
second_cnt++;
}
}
//cout << ma << " ma" << endl;
ll ans = 0;
for (ll i = 1; i <= hsy.cnt; i++) {
ll resy = numy[i];
//
ll ct1 = 0, ct2 = 0;
for (ll j : v[i]) {
if (numx[j] == ma) {
ct1++;
}
if (numx[j] == ma - 1) {
ct2++;
}
}
if (ct1 == cnt) {
if(resy + ma - 1 == res)
ans += cnt + second_cnt - ct2;
}
else {
if (resy + ma == res)
ans += cnt - ct1;
}
//cout << ans << " ans:" << endl;
}
printf("%lld ", res);
if (res == 2)return ans / 2;
else return ans;
}
int main() {
ll t;
scanf("%lld", &t);
ll ca = 0;
while (t--) {
ll n;
scanf("%lld", &n);
hsx.init(); hsy.init();
for (ll i = 1; i <= n; i++) {
numx[i] = 0;
numy[i] = 0;
v[i].clear();
scanf("%lld%lld", &x[i], &y[i]);
hsx.add(x[i]);
hsy.add(y[i]);
}
hsx.work(); hsy.work();
for (ll i = 1; i <= n; i++) {
x[i] = hsx.get(x[i]);
y[i] = hsy.get(y[i]);
numx[x[i]]++;
numy[y[i]]++;
v[y[i]].push_back(x[i]);
}
/*cout <<"hsx,hsy:"<< hsx.cnt << " " << hsy.cnt << endl;
for (ll i = 1; i <= n; i++) {
cout <<"(i,j) "<< x[i] << " " << y[i] << endl;
}*/
printf("Case %lld: ", ++ca);
ll ans = fun_ans();
printf("%lld\n", ans);
}
}
/*
20
5
1 2
1 3
2 3
4 5
6 7
3
1 2
2 3
3 1
*/ J Mr. Panda and Sequence Puzzle
题目链接
RSA解密，待补
L Ultra Weak Goldbach’s Conjecture
题目链接
题意：一个数分为六个素数和，求任意可行解。
思路：题目告诉一个偶数可以分为两个素数，一个奇数可以分为五个素数。
可以想到对于一个偶数可以分为 2+2+2+2+素数+素数。一个奇数可以分为3+2+2+2+素数+素数。枚举一个素数，判另一个素数即可。
#include <bits/stdc++.h>
#define maxn 1000005
typedef long long ll;
using namespace std;
ll x;
int prime[maxn];
ll p[maxn];
int tot;
void init(){
for(int i=2;i<=1000000;i++){
if(prime[i]==0)
p[++tot]=i;
for(int j=1;j<=tot&&i*p[j]<=1000000;j++){
prime[i*p[j]]=1;
if(i%p[j]==0)
break;
}
}
}
bool check(ll x){
for(ll i=2;i*i<=x;i++){
if(x%i==0)
return false;
}
return x!=1;
}
int main(){
int t;
init();
scanf("%d",&t);
for(int cas=1;cas<=t;cas++){
scanf("%lld",&x);
printf("Case %d: ",cas);
if(x<=11){
printf("IMPOSSIBLE\n");
continue;
}
if(x%2==0){
x-=8;
for(int i=1;i<=tot;i++){
// cout<<i<<" "<<p[i]<<" "<<x-p[i]<<endl;
if(check(1ll*(x-p[i])))
{
printf("%lld %lld 2 2 2 2\n",p[i],1ll*(x-p[i]));
break;
}
}
}else{
x-=9;
for(int i=1;i<=tot;i++){
if(check(x-p[i]))
{
printf("%lld %lld 2 2 2 3\n",p[i],1ll*(x-p[i]));
break;
}
}
}
}
}
京公网安备 11010502036488号