ZR十一青岛

A

题意

• 给你若干条直线，相邻的直线交点不能染相同的颜色。问将所有的交点染色至少要多少种颜色

• 给定直线的形式是在这条直线上的两个点的坐标

  思路

• 读完题纠结了一会怎么在二维上求出这些交点，只会 \(O(n^2)\) 暴力枚举两条直线，然后三维叉积
• 但是继续分析，发现我并不关心交点具体是多少，我们关心他们是否相邻，但这没有改变什么，还是要求坐标
• 那就在纸上画一下
• 发现如果这些直线围成三角形，那一定要三种颜色。
• 根据四色定理
• 是说二维平面上的不同区域，染色使相邻区域不同色，最少要用四种颜色
• 在这道题中，我们发现答案的取值是 1 2 3
• 而且我们发现这些直线中只要有3条斜率不相同的直线就可以构成一个三角形，一个三角形出现必须染3种颜色
• 所以答案是3的我们处理完了
• 当直线斜率只有2种时，答案是2

• 当直线斜率只有1种时，答案是1

细节

• 看一下我当时的赛时记录
  
• 最大的一个问题是
• 在多组数据输入时，不能在没读完数据就输出答案

### 关于三维叉积

100分代码

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<map>
#define ll long long 
using namespace std;
int T,n; 
ll a,b,c,d;
inline ll read(){
    ll s=0,w=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w; 
}
double k[4],kk;
int main() 
{
//  freopen("3.in","r",stdin);
//  freopen("3.o)
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        k[1]=0,k[2]=0,k[3]=0;
        int res=0;
        for(int i=1;i<=n;i++){
//          scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
            a=read();b=read();c=read();d=read();
            if(a==c) kk=192608017.794951;
            else kk=(double) (b-d)/(a-c);
            if(res==0) k[++res]=kk;
            else if(res==1){
                if(k[1]!=kk) k[++res]=kk;
            } 
            else if(res==2){
                if(kk!=k[1]&&kk!=k[2]){res=3;}
            }       
            else if(res==3) continue;
        }
        if(res==1||n==1||n==0) printf("0\n");
        else if(res==2&&n>2) printf("2\n");
        else if(res==3) printf("3\n");
        else if(res==2&&n==2)printf("1\n"); 
    }
    return 0;
}

B

题意

• 有一段序列每个元素有2个键值，\(p,t\)
• 最大化\(\sum_{i=1}^{n}{\frac{T-t_i}{T}*s_i}\)
• 但每个元素的键值可修改
• 共有 \(m\) 个
• 每次改变后重新计算答案(答案要求 \(*T\) 输出

思路

• 化式子
• \[\sum_{i=1}^n\frac{T-t_i}{T}p_i->T*\sum_{i=1}^np_i-\sum_{i=1}^np_i*t_i\]
• 发现前边的这个东西是个定值，我们只要最小化后边
• 考虑交换法
• 设到 \(i\) 和 \(j\) 前已经过了 \(x\) 的时间
• \((i,j)\) 这个顺序答案是
• \[x*p_i+(x+t_i)*p_j=x*p_i+x*p_j+p_j*t_i\]
• \((j,i)\)这个顺序答案是
• \[x*p_j+(x+t_j)*p_i=x*p_i+x*p_j+p_i*t_j\]
• 若 \((i,j)\) 这个顺序更优，则需要满足 \[p_i*t_j<p_j*t_i\]
• 即 \[\frac{p_i}{t_i}<\frac{p_j}{t_j}\]
• 所以我们要按照 \(\frac{p_i}{t_i}\) 排序
• 这样就有30分了
• 然后我们暴力更改
• 不过注意要求更该的是最初的序号，所以我们要记录一下最初的id
• 不过在这个地方我们直接暴力寻找是O(n) 的，但是经yzz的启发，成功再拍了一遍序，成功变成O(nlogn) 的了
• 所以70是很容易的，挂成50是很惨的

70代码

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<map>
#define N 100005
#define ll long long 
using namespace std;
int n,m;
ll T,s,tim,res;
struct node{
    int id;
    ll p,t;
}d[N];
bool cmp(node a,node b){
    return a.p *b.t >b.p *a.t ;
}
bool cmp1(node a,node b){
    return a.id <b.id;
}
int main()
{
    scanf("%d%d%lld",&n,&m,&T);
    for(int i=1;i<=n;i++) d[i].id =i,scanf("%lld%lld",&d[i].p,&d[i].t);
    sort(d+1,d+n+1,cmp);
    for(int i=1;i<=n;i++) s+=d[i].p ,tim+=d[i].t ,res+=tim*d[i].p ;
    printf("%lld\n",s*T-res);
    while(m--){
        int x;
        ll a,b;
        s=0,tim=0,res=0;
        scanf("%d%lld%lld",&x,&a,&b);
        for(int i=1;i<=n;i++) if(d[i].id==x) {d[i].p=a,d[i].t =b;break;}  
//      sort(d+1,d+n+1,cmp1);
//      d[x].p =a,d[x].t =b;
        sort(d+1,d+n+1,cmp);
        for(int i=1;i<=n;i++) s+=d[i].p ,tim+=d[i].t ,res+=tim*d[i].p ;
        printf("%lld\n",s*T-res);
    }
    return 0;
}

ZR青岛

原文：https://www.cnblogs.com/Vimin/p/11645148.html