2022ZJCPC 部分题目

G

题目链接：2022ZJCPC G

要求从一点到另一点的最短时间，可转化为求一点到另一点的最短路。

只需要预处理一点到另一点的距离，分为从原点与终点出发的和从其他点出发的即可，其他点出发的会有三秒的加速。

最后求一个最短路即可。

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define ld long double
using namespace std;
struct node{
	double x,y;
};
struct dis{
	int u;
	double w;
};
double v1,v2;
const int MAXN=1e3+5;
node point[MAXN];
int vis[MAXN];
double dis1[MAXN];
vector<dis>arr[MAXN];
double distance(struct node x,struct node y){
	double ans=pow((x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y),0.5);
	return ans;
}
int n;
void dijkstra(int n, int s) {
    fill(dis1,dis1+MAXN,10000000000);
    dis1[s] = 0;
    for (int i = 1; i <= n; i++) {
        int u = 0, mind = 1e9;
        for (int j = 1; j <= n; j++){
            if (!vis[j] && dis1[j] < mind) u = j, mind = dis1[j];
            }
        vis[u] = true;
        for (auto ed : arr[u]) {
            int v = ed.u;
            double w = ed.w;
            if (dis1[v] > dis1[u] + w) dis1[v] = dis1[u] + w;
        }
    }
}
int main(){
	cin>>n;
	for(int i=1;i<=n+2;i++){
		cin>>point[i].x>>point[i].y;
	}
	cin>>v1>>v2;
	dis index;
	for(int i=n+1;i<=n+2;i++){
		for(int j=1;j<=n+2;j++){
			index.u=j;
			index.w=distance(point[i],point[j])/v1;
			arr[i].push_back(index);
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n+2;j++){
			index.u=j;
			if(distance(point[i],point[j])/v2<=3){
				index.w=distance(point[i],point[j])/v2;
			}
			else {
				index.w=3+(distance(point[i],point[j])-3*v2)/v1;
			}
			arr[i].push_back(index);
		}
	}
	dijkstra(n+2,n+1);
	printf("%lf",dis1[n+2]);
}

L

题目链接：2022ZJCPC J

假设最后集合的平均数为k，则无脑选择小于等于k的数，对大于k的数从小开始取。

故对数sort后，所选择的序列必定是一个前缀。

可先确定前缀，最后用upper_bound确定大于平均数的数量。

由于是1e6数量的1e9大小的输入，需要读入优化。(因为没优化T过)

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define ld long double
using namespace std;
int n;
int arr[1000005];
ll pre[1000005];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>arr[i];
	}
	sort(arr+1,arr+1+n);
	for(int i=1;i<=n;i++){
		pre[i]=pre[i-1]+arr[i];
	}
	int maxn=0;
	for(int i=1;i<=n;i++){
		ll index=pre[i]/i;
		int sum=upper_bound(arr+1,arr+i,index)-arr-1;
		sum=i-sum;
		maxn=max(sum,maxn);
	}
	cout<<maxn;
}
 

M

题目链接：2022ZJCPC M

设中心图像（黑格包裹的白格）为x，可以统计黑白格的数量，进行解方程，解得两种图形的数量。

注意在query的时候要检测6x6的方格，而不是4x4。

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define ld long double
using namespace std;
int a,b;
char arr[1005][1005];
char vis[][7]=
{
    "######",
    "##..##",
    "#....#",
    "#....#",
    "##..##",
    "######"
};
 
bool query(int i,int j){
	if(i+5>a||j+5>b){
		return 0;
	}
	for(int p=0;p<=5;p++){
        for(int q=0;q<=5;q++){
            if(arr[i+p][j+q]!=vis[p][q])return 0;
        }
    }
    return 1;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>a>>b;
	int black=0;
	int white=0;
	int hole=0;
	for(int i=1;i<=a;i++){
		for(int j=1;j<=b;j++){
			cin>>arr[i][j];
			if(arr[i][j]=='#')black++;
			else white++;
		}
	}
	for(int i=1;i<=a;i++){
		for(int j=1;j<=b;j++){
			if(query(i,j))hole++;
		}
	}
	int x=(100*hole-black)/54;
	int y=hole-2*x;
	cout<<x<<' '<<y;
    return 0;
}

其实有更简单暴力的方法就是每次query成功后直接对(i+7 , j) (i-7 , j) (i , j-7) (i , j+7)进行query，

如果有一个成立那么x++，如果没有，那么y++。

由于x算了两次，最后x需要除2。

最后直接输出x与y。

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define ld long double
using namespace std;
int a,b;
char arr[1005][1005];
char vis[][7]=
{
    "######",
    "##..##",
    "#....#",
    "#....#",
    "##..##",
    "######"
};
 
bool query(int i,int j){
	if(i+5>a||j+5>b){
		return 0;
	}
	for(int p=0;p<=5;p++){
        for(int q=0;q<=5;q++){
            if(arr[i+p][j+q]!=vis[p][q])return 0;
        }
    }
    return 1;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>a>>b;
	int x=0;
    int y=0;
	for(int i=1;i<=a;i++){
		for(int j=1;j<=b;j++){
			cin>>arr[i][j];
		}
	}
	for(int i=1;i<=a;i++){
		for(int j=1;j<=b;j++){
			if(query(i,j)){
                if(i+7<=a&&query(i+7,j))x++;
                else if(i-7>=1&&query(i-7,j))x++;
                else if(j-7>=1&&query(i,j-7))x++;
                else if(j+7<=b&&query(i,j+7))x++;
                else y++;
            }
		}
	}
	cout<<x/2<<' '<<y;
    return 0;
}