CCPC2022 威海站 个人简要题解
没有写题欲望……来补补题整理一下思路
和队友开的 7-1138
Dashboard - 2022 China Collegiate Programming Contest (CCPC) Weihai Site - Codeforces
A
会读题就会做。考虑对于每个位置求出来一个
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define x first
#define y second
using namespace std;
const int N=1e6+10;
set<string> se;
int f[10][2];
void slove(){
int n;cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=5;j++){
string s;cin>>s;se.insert(s);
}
}
int m;cin>>m;
for(int i=1;i<=m;i++){
string s;cin>>s;int op;cin>>op;
if(se.count(s)){
f[op][0]++;
}else f[op][1]++;
}
int ans=0;
for(int i=1;i<=5;i++){
int mx=1e9+10;
for(int j=1;j<=5;j++)
if(i!=j){
mx=min(f[j][0]+f[j][1],mx);//别的位置能删的最多的
}
int no=min(f[i][0],mx);
ans+=no;
f[i][0]-=no;
for(int j=1;j<=5;j++)
if(i!=j){
if(f[j][1]>=no) f[j][1]-=no;
else {
f[j][0]-=(no-f[j][1]);
f[j][1]=0;
}
}
}
cout<<ans<<endl;
}
signed main(){
ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
int T=1;
while(T--) slove();
}
C
分类讨论不难发现:其实只需要存在五点不共线就可以了。
如果不存在三点共线:选
三点共线:考虑直线
四点共线:对于直线
代码队友写的捏
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define x first
#define y second
using namespace std;
const int N=2e5+10;
const double eps=1e-9;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
PII a[N];
PII c[10];
void slove(){
int n;cin>>n;
for(int i=1;i<=n;i++){cin>>a[i].x>>a[i].y;}
if(n<5){
cout<<"NO"<<endl;
return ;
}
for(int i=1;i<=5;i++) c[i]=a[i];
for(int i=6;i<=n;i++){
if((a[i-1].y-a[i-2].y)*(a[i].x-a[i-2].x)!=(a[i].y-a[i-2].y)*(a[i-1].x-a[i-2].x)){
int num=5;
for(int j=i;j>i-5;j--) c[num--]=a[j];
break;
}
}
set<PDD> se;
int ji=0;
// for(int i=1;i<=5;i++){
// cout<<c[i].x<<" "<<c[i].y<<endl;
// }
for(int i=1;i<=5;i++){//ÒÔiΪ»ùµã
se.clear();
bool ok=true;
for(int j=1;j<=5;j++)
if(j!=i){
int x=c[i].x-c[j].x,y=c[i].y-c[j].y;
double len=sqrtl(x*x*1.0+y*y*1.0);
double x1=x*1.0/len,y1=y*1.0/len;
if(se.size()){
for(auto zz:se){
if(fabs(zz.x-x1)<eps&&fabs(zz.y-y1)<eps){
ok=false;
break;
}
}
}
se.insert({x1,y1});
if(!ok) break;
}
if(ok){
ji=i;
break;
}
}
if(ji){
cout<<"YES"<<endl;
cout<<c[ji].x<<" "<<c[ji].y<<endl;
for(int i=1;i<=5;i++)if(i!=ji){
cout<<c[i].x<<" "<<c[i].y<<endl;
}
}
else cout<<"NO"<<endl;
}
/*
1
6
1 1
2 2
3 3
5 5
6 7
6 6
*/
signed main(){
ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
int T=1;cin>>T;
while(T--) slove();
}
D
神秘跳棋题……
这个题发现,实际上有用的情况至多只有
但是要注意的是,前两排,第三排,后两排对应的六联通坐标不一样,很坑人。
以及记得这个题的状态
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cctype>
#include <vector>
#include <cmath>
#include <queue>
#define pii pair<int,int>
#define mp make_pair
#define ll long long
using namespace std;
const int N = 1e6 + 10;
int a[10][10],f[N],qwq[10][10];
bool vis[N];
const int dx1[6] = {1,-1,-1,1,0,0};
const int dy1[6] = {1,-1,0,0,-1,1};
const int dx2[6] = {1,-1,-1,1,0,0};
const int dy2[6] = {0,0,1,-1,-1,1};
const int dx3[6] = {1,-1,-1,1,0,0};
const int dy3[6] = {0,-1,0,-1,-1,1};
pii sta[20];
bool valid(int x,int y) {
if (x < 1 || y < 1 || x > 5 || y > 5) return 0;
int r = 2;
if (x <= 3) r += x;
else if (x == 4) r += 2;
else r++;
if (y <= r) return 1;
else return 0;
}
pii getnxt(int x,int y,int typ) {
if (x < 3) {
int nx = dx1[typ] + x,ny = y + dy1[typ];
return mp(nx,ny);
} else if (x > 3){
int nx = dx2[typ] + x,ny = y + dy2[typ];
return mp(nx,ny);
} else {
int nx = dx3[typ] + x,ny = y + dy3[typ];
return mp(nx,ny);
}
}
int dfs(int now) {
if (vis[now]) return f[now];
int ans = 0;
int ma[10][10];
vector <pii> st;
for (int i = 0;i < 20;++i) {
pii ps = sta[i];
if (now & (1 << i)) {
ma[ps.first][ps.second] = 1;
st.push_back(ps);
} else {
ma[ps.first][ps.second] = 0;
}
}
if (st.size() == 1) {
f[now] = 0;
vis[now] = 1;
return 0;
}
/*cout << "nowst:" << now << ":\n";
for (int i = 1;i <= 5;++i) {
int r = 2;
if (i <= 3) r += i;
else if (i == 4) r += 2;
else r += 1;
for (int j = 1;j <= r;++j) {
cout << ma[i][j];
}
cout <<"\n";
}*/
for (auto p : st) {
int x = p.first,y = p.second;
for (int i = 0;i < 6;++i) {
pii np = getnxt(x,y,i);
int nx = np.first,ny = np.second;
//for (int j = 0;j < 6;++j) {
pii npp = getnxt(np.first,np.second,i);
int nxx = npp.first,nyy = npp.second;
//printf("i:%d (%d,%d)->(%d,%d)->(%d,%d)\n",i,x,y,nx,ny,nxx,nyy);
if (valid(nx,ny) && valid(nxx,nyy) && ma[nx][ny] > 0 && (!(nxx == x && nyy == y))){
//printf("i:%d (%d,%d)->(%d,%d)->(%d,%d)\n",i,x,y,nx,ny,nxx,nyy);
int jpst = now;
jpst -= (1 << qwq[x][y]);
jpst -= (1 << qwq[nx][ny]);
jpst |= (1 << qwq[nxx][nyy]);
if (f[jpst]) ans = max(ans,f[jpst] + a[nx][ny]);
else ans = max(ans,dfs(jpst) + a[nx][ny]);
}
//}
}
}
//cout << "ans = " << ans << "\n";
vis[now] = 1;
return f[now] = ans;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int cnt = 0;
for (int i = 1;i <= 5;++i) {
int r = 2;
if (i <= 3) r += i;
else if (i == 4) r += 2;
else r += 1;
for (int j = 1;j <= r;++j) {
cin >> a[i][j];
qwq[i][j] = cnt;
sta[cnt++] = mp(i,j);
}
}
int q;cin >> q;
//cout << dfs(17408);
//return 0;
while (q--) {
int cnt = 0;
int stat = 0;
for (int i = 1;i <= 5;++i) {
int r = 2;
if (i <= 3) r += i;
else if (i == 4) r += 2;
else r += 1;
for (int j = 1;j <= r;++j) {
char c;cin >> c;
if (c == '#') stat += (1 << cnt);
++cnt;
}
}
if (vis[stat]) cout << f[stat] << "\n";
else cout << dfs(stat) << "\n";
}
return 0;
}
/*
9 2 2
3 3 7 2
0 3 6 8 5
4 7 7 5
8 0 7
1
...
..#.
..##.
....
...
*/
E
发现这东西是收敛很快的一次分段函数,暴力计算就完了。
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n,a[N],k;
signed main() {
cin >> n >> k;
for (int i = 1;i <=n;++i) cin >> a[i];
int pos = 0;
for (int i = 1;i <= n;++i) {
if (a[i] < k) {
pos = i;
break;
}
}
if (pos) {
printf("Python 3.%d will be faster than C++",pos);
return 0;
}
int qwq = a[n] - a[n-1];
if (qwq >= 0) {
puts("Python will never be faster than C++");
} else {
for (int i = n+1;i <= 200000;++i) {
a[i] = max(0,2*a[i-1] - a[i-2]);
//cout << a[i] << " " << i << "\n";
if (a[i] < k) {
pos = i;
break;
}
}
printf("Python 3.%d will be faster than C++",pos);
}
return 0;
}
G
神秘打表题。
主要是得发现,这个东西有一个
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define x first
#define y second
using namespace std;
const int N=4e6+10;
int s[N];
int p=1;
int check(int r){
return s[p]*(r/p)+s[r%p];
}
void slove(){
int x,n;cin>>x>>n;
while(p<x) p*=2;
//cout<<p<<endl;
for(int i=1;i<=p;i++){
int no=__gcd((i*x)^x,x);
if(no==1) s[i]=1;
else s[i]=0;
}
for(int i=1;i<=p;i++) s[i]+=s[i-1];
int ans=0;
while(n--){
int l,r;cin>>l>>r;
cout<<check(r)-check(l-1)<<endl;
}
}
/*
999999 1
1 1000000000000
462890624994
*/
signed main(){
ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
int T=1;
while(T--) slove();
}
I
好厉害的贪心题!叶天帝写的,摆了。
#include<bits/stdc++.h>
#define int __int128
#define ll long long
#define endl '\n'
#define x first
#define y second
using namespace std;
const int N=5e4+10;
int a[N],b[N],c[N];
int po[N];
ll n,k;
bool check(int x){
for(int i=0;i<=k;i++) c[i]=b[i];
priority_queue<int,vector<int>, less<int>> heap;
for(int i=1;i<=n;i++){
if(x)heap.push(a[i]*x);
}
int num=0;
for(int i=k-1;i>=0;i--){//从高位往低位填充
// cout<<po[i]<<" "<<endl;
while(heap.size()){
int p=heap.top();
// cout<<(ll)p<<" ";
heap.pop();
if(p<po[i]&&c[i]){
c[i]--;
p=0;
// continue;
}
int no=p/po[i];
if(c[i]>=no){
// cout<<(ll)p<<endl;
c[i]-=no;
p-=no*po[i];
}else {
p-=c[i]*po[i];
c[i]=0;
}
// cout<<(ll)p<<" "<<(ll)i<<" "<<c[i]<<" "<<endl;
if(p) heap.push(p);
if(!c[i]) break;
}
}
if(heap.size()) return false;
return true;
}
void slove(){
cin>>n>>k;
for(int i=1;i<=n;i++)
{
ll x;cin>>x;a[i]=x;
}
for(int i=0;i<k;i++){
ll x;cin>>x;b[i]=x;
}
int l=0,r=1e18;
// cout<<check(5)<<endl;
while(l<r){
int mid=(l+r+1)/2;
// cout<<mid<<" "<<check(mid)<<" "<<l<<" "<<r<<endl;
if(check(mid)) l=mid;
else r=mid-1;
}
ll ans=l;
cout<<ans<<endl;
}
signed main(){
ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
po[0]=1;
for(int i=1;i<=30;i++) po[i]=po[i-1]*2;
ll T=1;cin>>T;
while(T--) slove();
}
J
潘哥给的思路,但是写不出来被硬控 1h。
其实发现可以计算出最优方案的答案,然后看奇偶性就好了
#include <bits/stdc++.h>
#define pii pair<int,int>
#define mp make_pair
#define ll long long
#define int long long
#define x first
#define y second
using namespace std;
const int N = 2e5 + 10;
//偶数为0
typedef pair<int,int> PII;
int n,k;
int a[N];
PII li[N];
map<int,int> num,c;
void solve() {
cin >> n >> k;
num.clear(),c.clear();
for(int i=1;i<=n;i++){cin>>a[i];}
sort(a+1,a+1+n);
for(int i=1;i<=k;i++)cin>>li[i].x>>li[i].y;
sort(li+1,li+1+k);
vector<PII> val;
int ls=-1;//-1不能等于0
for(int i=1;i<=k;i++){
if(li[i].y==0){
val.push_back({ls,li[i].x-1});
ls=li[i].x;
}
}
val.push_back({ls,1e9});//多设一点
for(int i=1;i<=k;i++) num[li[i].x]=li[i].y;//限制
//找处于这个区间内的数
int l=0;
int step=0;
for(int i=1;i<=n;i++){
int st=i;
int lst=val[l].x+1;//能放的位置
while(a[st]<val[l].x&&st<=n) st++;
if(st>n){
break;
}
// cout<<val[l].x<<" "<<val[l].y<<endl;
while(1){
if(st>n) break;
if(lst>val[l].y)break;
if(a[st]>val[l].y) break;
if(!num[lst]) num[lst]=1e9;
//把a[i]变成lst
c[lst]++;
step+=a[st]-lst;
// cout<<st<<" "<<lst<<endl;
if(c[lst]==num[lst])lst++;
st++;
}
l++;
i=st-1;
}
// cout<<step<<endl;
if(step%2) cout<<"Pico"<<endl;
else cout<<"FuuFuu"<<endl;
}
signed main() {
ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
int T;cin >> T;
while (T--) solve();
}
本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可。
评论已关闭