2021上海市赛【10.10训练补题】

 Dashboard - The 2021 Shanghai Collegiate Programming Contest - Codeforces

参考题解：2021CCPC上海省赛题解ABCDEGHIJK_2021ccpc上海题解_Hytidel的博客 

A. 小 A 的点面论（数学几何）

题解：求平面的法向量（外积法）

代码：

#include
using namespace std;
typedef long long ll;
typedef double db;
typedef __int128 i128;
const int N=1e5+5;
const i128 mod=998244353;
const int inf=1<<30;
 
int x1,x2,y1,y2,x3,y3,z1,z2,z3;
int main(){
	scanf("%d%d%d%d%d%d",&x1,&y1,&z1,&x2,&y2,&z2);
	x3=y1*z2-y2*z1;
	y3=-(x1*z2-x2*z1);
	z3=x1*y2-x2*y1;
	printf("%d %d %d",x3,y3,z3);
}

G. 鸡哥的雕像 

 题解：当a[ i ]中有一个998244353出现，雕像放在 i 处的答案为其他数的乘积，放在其他处的答案为0；当a[ i ]中有两个及以上998244353出现，所有答案为0

代码：

#include
using namespace std;
typedef long long ll;
typedef double db;
typedef __int128 i128;
const int N=1e5+5;
const i128 mod=998244353;
const int inf=1<<30;
 
i128 n;
inline i128 quickp(i128 base,i128 pow){
	i128 res=1;
	while(pow){
		if(pow&1)res=res*base%mod;
		pow>>=1;
		base=base*base%mod;
	}return res;
} 
inline i128 inv(i128 x){
	return quickp(x,mod-2);
}
inline i128 read(){  //__int128 可以换成 int longlong 基于自己的需求即可
    i128 x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}
inline void out(i128 x){    //输出
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9)
        out(x/10);
    putchar(x%10+'0');
}
 
i128 a[N];
i128 res=1;
int main(){
	n=read();int cnt=0;
	for(i128 i=1;i<=n;i++){
		a[i]=read();
		if(a[i]!=mod) res=res*a[i]%mod;
		else cnt++;
	}
	if(cnt){
		for(i128 i=1;i<=n;i++){
			if(a[i]==mod&&cnt==1){
				out(res);printf(" ");
			}else printf("0 ");
		}
	}
	else{
		for(i128 i=1;i<=n;i++){
			out(res*inv(a[i])%mod);printf(" ");
		}
	}
}

H. 鸡哥的 AI 驾驶（二分）

题解：

若会发生事故,则时间越久越可能发生事故,故是否发生事故的性质具有二段性,可二分出其分界点.

考虑如何check.显然两不同型号的车发生事故的充要条件是它们的相互位置发生改变,即直观上它们互相穿过了对方.注意到每辆车不发生事故的移动范围是数轴上该型号的车最左边与最右边的位置之间的线段,则某型号的车离开该范围也会发生事故.

考察二分时间的范围.显然耗时最久的是从x=−1e9以速度v=1走到x=1e9,耗时t=2e9,则边界可取[0,2e9+1],其中+1是为了退出循环后断定l=2e9是否有解.

代码：

#include
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int>pi;
const int mod=1e9+7;
const int N=1e5+5;
inline ll read(){
    ll x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}
int n,k;
ll res=-1;
struct node{
	ll x,v;
	int id;
	bool operator<(const node&B)const{
		if(x!=B.x)return x
		return v
	}
}a[N];
int seg[N][3];
pairint>tx[N];//{tx,id}
int chk(ll t){//[0,t]不会撞车 
	for(int i=1;i<=n;i++){
		tx[i]={a[i].x+t*a[i].v,i};
	}sort(tx+1,tx+1+n);
	
	//检查同一位置是否有不同编号，同一编号区间的车辆是否超出区间
	for(int i=2;i<=n;i++){
		//printf("tx[%d].x:%lld id:%d\n",i,tx[i].first,tx[i].second);
		if(tx[i].first==tx[i-1].first&&tx[i].second!=tx[i-1].second)return 0;
	} for(int i=1;i<=n;i++){
		//printf("i%d seg[%d]l:%d r:%d\n",i,tx[i].second,seg[tx[i].second][1],seg[tx[i].second][2]);
		if(i1]||i>seg[tx[i].second][2])return 0;
	}return 1;
}
//1 1 2 2 2 1 1
//[1,2][3,5][6,7]
int main(){
    n=read();k=read();
    for(int i=1;i<=n;i++){
    	a[i].x=read();a[i].v=read();a[i].id=read();
	} 
	sort(a+1,a+n+1);
	//预处理区间
	seg[1][1]=1;seg[n][2]=n;
	for(int i=2;i<=n;i++){
		if(a[i].id==a[i-1].id)seg[i][1]=seg[i-1][1];
		else seg[i][1]=i;
	} 
	for(int i=n-1;i>=1;i--){
		if(a[i].id==a[i+1].id)seg[i][2]=seg[i+1][2];
		else seg[i][2]=i;
	}
	
	ll l=0,r=2e9+1;
	while(l<=r){
		ll mid=(l+r)/2;
		//printf("mid:%lld res%lld\n",mid,res);
		if(chk(mid))res=mid,l=mid+1;
		else r=mid-1;
	}if(res!=2e9+1)printf("%lld",res);
	else printf("-1");
	return 0;
}

J. Alice and Bob-1（贪心）

题解：

Alice要 |A|-|B| 尽量大，Bob要 |A|-|B|尽量小  <=>  两人每次都选择尽量大的数字

如：-8 -7 -5  -3 1 3     Alice：-8 -5 1=12  Bob：-7 -3 3=7

所以可能先选正值最大，也可能先选负值最大，Alice先手则考虑更利于Alice的情况，即在两人每次都选择最大值的情况下 |A|-|S-A| 最大

代码：

#include
using namespace std;
typedef long long ll;
typedef double db;
const int mod=1e9+7;
const int N=1e5+5;
inline ll read(){
    ll x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}
ll a[5005];
ll n,s1,s2,s;
int main(){
    n=read();
    
    for(int i=1;i<=n;i++){
    	a[i]=read();
    	s+=a[i];
	} 
	sort(a+1,a+n+1);
	int f=1;
	for(int i=n;i>=1;i-=2)s1+=a[i];
	for(int i=1;i<=n;i+=2)s2+=a[i];
	
	ll res=max(abs(s1)-abs(s-s1),abs(s2)-abs(s-s2));
	printf("%lld",res);
}