2023年icpc网络赛第一场七题代码-526互联

模拟题

首先跑一遍，得到校排名

然后对两个比赛的校排名进行合并即可

#include<bits/stdc++.h>
using namespace std;
int n,m;
map<string,int>o;
string s[10010];
vector<string>a,b;
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>s[i];
        if(o[s[i]]==0)
        {
            o[s[i]]=1;
            a.push_back(s[i]);
        }
    }
    o.clear();
    for(int i=1;i<=m;i++)
    {
        cin>>s[i];
        if(o[s[i]]==0)
        {
            o[s[i]]=1;
            b.push_back(s[i]);
        }
    }
    o.clear();
    int i=0,j=0;
    while(i<a.size()&&j<b.size())
    {
        if(o[a[i]]==0)
        {
            cout<<a[i]<<'\n';
            o[a[i]]=1;
        }
        i++;
        if(o[b[j]]==0)
        {
            cout<<b[j]<<'\n';
            o[b[j]]=1;
        }
        j++;
    }
    while(i<a.size())
    {
        if(o[a[i]]==0)
        {
            cout<<a[i]<<'\n';
            o[a[i]]=1;
        }
        i++;
    }
    while(j<b.size())
    {
        if(o[b[j]]==0)
        {
            cout<<b[j]<<'\n';
            o[b[j]]=1;
        }
        j++;
    }
}

考虑每个连通块内部，如果边数=(siz-1)*siz/2，则证明是一个完全图，否则可以计算出这个连通块还需要几个边才能变成完全图

因为至少要加一条边，则当全部连通块都是完全图时，不得不连接两个连通块，此时只需要找点数最少的两个连通块连一下，边数为点数之积

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N= 1e6 + 9;

int n, m, f[N];
ll  sze[N], d[N],vis[N],ssz[N];
vector<pair<int,int> >ve;

int find(int x) {
    return x == f[x] ? x : f[x] = find(f[x]);
}

int main() {
    ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    for(int i=1;i<=n;++i) sze[i]=1,f[i]=i; 
    for (int i = 1, u, v; i <= m; ++i) {
        cin >> u >> v;
        d[u]++;d[v]++;
        ve.push_back({u,v});
    }
    for(auto t:ve)
    {    
        int u=t.first,v=t.second;
        int fu = find(u), fv = find(v);
        if (fu != fv) {
            sze[fv]+=sze[fu];
            d[fv]+=d[fu];
            f[fu]=fv;
        }
    }
    bool flag=false;
    int tot=0;
    ll ans=0;
    for(int i=1;i<=n;++i)
    {
        int ti=find(i);
        if(!vis[ti])
        {
            vis[ti]=1;
            // cout<<ti<<' '<<sze[ti]<<' '<<d[ti]<<endl;
            if(1ll*sze[ti]*(sze[ti]-1)==d[ti])
            {
                ssz[++tot]=sze[ti];
            }
            else 
            {
                flag=true;
                ans+=1ll*sze[ti]*(sze[ti]-1)/2-d[ti]/2;
            }
        }
    }
    if(flag)
    {
        cout<<ans<<endl;
        return 0;
    }
    // cout<<tot<<endl;
    sort(ssz+1,ssz+tot+1);
    ll t1=ssz[1]+ssz[2],dt=1ll*ssz[1]*(ssz[1]-1)/2+1ll*ssz[2]*(ssz[2]-1)/2;
    // cout<<t1<<' '<<dt<<endl;
    cout<<t1*(t1-1)/2-dt<<endl;
    return 0;
}

写了个找规律的dfs，没找到规律

map<int,map<int,int>>o[10000];
int dfs(int x,int y,int z)
{
    if(x>y)
        swap(x,y);
    if(x>z)
        swap(x,z);
    if(y>z)
        swap(y,z);
    y-=x;
    z-=x;
    x=0;
    if(o[x][y][z])
    {
        return o[x][y][z];
    }
    for(int i=1;i*2<=y;i++)
        if(dfs(x+i,y-i,z)==-1)
            return o[x][y][z]=1;
    for(int i=1;i*2<=z;i++)
        if(dfs(x+i,y,z-i)==-1)
            return o[x][y][z]=1;
    for(int i=1;i+y+i<=z;i++)
        if(dfs(x,y+i,z-i)==-1)
            return o[x][y][z]=1;
    return o[x][y][z]=-1;
}

考虑对着第一个图，挨个看每条边。如果当前xy所在的连通块，在第二个图里有连边，则需要把这条边加上，概率*=x所在的连通块的数量*y所在的连通块的数量

若无连边，则直接输出0即可

可以发现需要对某一个连通块里的所有点，扫描出边。边的数量是O(n)的，利用边的数量进行启发式合并即可。

#include <bits/stdc++.h>
#define ll long long
#define rep(x,y,z) for(int x=y;x<=z;++x)
using namespace std;
char buf[1<<15],*fs,*ft;
char getc()
{
    return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;
}
int read()
{
    int This=0;
    char ch=getc();
    while(ch<'0'||ch>'9')
        ch=getc();
    while(ch>='0'&&ch<='9')
    {
        This=(This<<1)+(This<<3)+ch-'0';
        ch=getc();
    }
    return  This;
}
const int N=1e6+10,P=998244353;
int n,f[N],sze[N],tot,head[N];
pair<int,int> ve[N];
int Head[N],Next[N],v[N],End[N];
int sum[N];
inline ll power(ll x,ll y)
{
    ll ans=1;
    while(y)
    {
        if(y&1) ans=ans*x%P;
        y>>=1;
        x=x*x%P;
    }
    return ans;
}
struct edge
{
    int next,y;
}e[2*N];
void add(int x,int y)
{
    tot++;
    e[tot]={head[x],y};
    head[x]=tot;
}
inline int find(int x)
{
    return x==f[x]?x:f[x]=find(f[x]);
}

int main() {
//    freopen("1.in","r",stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    n=read();
    rep(i,1,n) f[i]=i,sze[i]=1,Head[i]=i,End[i]=i,Next[i]=0;
    rep(i,1,n-1)
    {
        int u,v;
        u=read();v=read();
        ve[i]={u,v};
    }
    rep(i,1,n-1)
    {
        int u,v;
        u=read();v=read();
        add(u,v);
        add(v,u);
        sum[u]++;
        sum[v]++;
    }
    ll ans=1;
    for(int i=1;i<n;i++)
    {
        auto t=ve[i];
        int t1=find(t.first),t2=find(t.second);
        if(sum[t1]>sum[t2]) swap(t1,t2);
        bool flag=false;
        for(int x=Head[t1];x;x=Next[x])
        {
            for(int j=head[x];j;j=e[j].next)
            {
                int y=e[j].y;
                if(find(y)==t2)
                {
                    flag=true;
                    break;
                }
            }
            if(flag) break;
        }
        if(!flag)
        {
            cout<<0;
            return 0;
        }
        ans=ans*power(sze[t1],P-2)%P*power(sze[t2],P-2)%P;
        Next[End[t2]]=Head[t1];
        End[t2]=End[t1];
        sze[t2]+=sze[t1];
        f[t1]=t2;
        sum[t2]+=sum[t1];
    }
    cout<<ans;
    return 0;
}

可以状压dp一下，f[i][j][k]表示到了第i个位置，选了密码j，小写、大写、数字是否选过的情况为k。进行dp时，可以发现状态数大概是5e7，需要用前缀和优化一下，不能枚举第i位选什么、第i+1位选什么进行dp。

以及空间给的不太多，需要滚动数组一下

总的来说是状压dp+前缀和优化+滚动数组大乱炖

#include <bits/stdc++.h>
#define ll long long
using namespace std;
char s[100010];
int f[100010][100][10],n,mod=998244353;
ll sum[10];
int main() {
    // freopen("1.in","r",stdin);
    scanf("%d",&n);
    scanf("%s",s+1);

    f[0][63][0]=1;
    for(int i=0;i<n;i++)
    {
        for(int j=1;j<=63;j++)
            for(int k=0;k<8;k++)
                f[(i+1)&1][j][k]=0;
        for(int k=0;k<8;k++)
            sum[k]=0;
        for(int j=1;j<=63;j++)
        {
            for(int k=0;k<8;k++)
            {
                sum[k]=sum[k]+f[i&1][j][k];
                if(sum[k]>=mod)
                    sum[k]-=mod;
            }
        }
            for(int k=0;k<8;k++)
            {
                if(s[i+1]=='?')
                {
                    for(int x=1;x<=26;x++)
                    {
                        f[(i+1)&1][x][k|1]=((sum[k]-f[(i&1)][x][k]+f[(i+1)&1][x][k|1])%mod+mod)%mod;
                    }
                    for(int x=27;x<=52;x++)
                    {
                        f[(i+1)&1][x][k|2]=((sum[k]-f[(i&1)][x][k]+f[(i+1)&1][x][k|2])%mod+mod)%mod;
                    }
                    for(int x=53;x<=62;x++)
                    {
                        f[(i+1)&1][x][k|4]=((sum[k]-f[(i&1)][x][k]+f[(i+1)&1][x][k|4])%mod+mod)%mod;
                    }
                }
                if('a'<=s[i+1]&&s[i+1]<='z')
                {
                    int x=s[i+1]-'a'+1;
                    f[(i+1)&1][x][k|1]=((sum[k]-f[(i&1)][x][k]+f[(i+1)&1][x][k|1])%mod+mod)%mod;
                    x=s[i+1]-'a'+27;
                    f[(i+1)&1][x][k|2]=((sum[k]-f[(i&1)][x][k]+f[(i+1)&1][x][k|2])%mod+mod)%mod;
                }
                if('0'<=s[i+1]&&s[i+1]<='9')
                {
                    int x=s[i+1]-'0'+53;
                    f[(i+1)&1][x][k|4]=((sum[k]-f[(i&1)][x][k]+f[(i+1)&1][x][k|4])%mod+mod)%mod;
                }

                if('A'<=s[i+1]&&s[i+1]<='Z')
                {
                    int x=s[i+1]-'A'+27;
                    f[(i+1)&1][x][k|2]=((sum[k]-f[(i&1)][x][k]+f[(i+1)&1][x][k|2])%mod+mod)%mod;
                    
                }
            }
        }
    }
    int ans=0;
    for(int i=1;i<63;i++)
    {
        ans=f[n&1][i][7]+ans;
        if(ans>=mod)
            ans-=mod;
    }
    cout<<ans;
}

因为两个圆的位置的特殊性，考虑对x和y分别考虑，期望距离就是|x-x|+|y-y|，为所选的点和圆心的曼哈顿得距离，所以把两个圆变换一下位置，变成一个圆位于原点，另一个圆位于右上角，则所选的点应该是(x-r/sqrt(2),y-sqrt(2))，也就是y=-x+k与右上角圆的相切的位置。

#include <bits/stdc++.h>
using namespace std;

double dist(double x, double y, double _x, double _y) {
    return sqrt((x - _x) * (x - _x) + (y - _y) * (y - _y));
}

struct circle {
    int x1, x2, y1, y2;
    double R, xo, yo;
    

    
    void read() {
        // cin >> x1 >>y1 >> x2 >> y2;
        scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
    }

    void init() {
        read();
        xo = (1.0 * x1 + x2) / 2;
        yo = (1.0 * y1 + y2) / 2;
        R = dist(x1, y1, x2, y2);
    }
} C[3];


void solve() {
    C[1].init();
    C[2].init();
    C[2].xo -= C[1].xo;
    C[2].yo -= C[1].yo;
    C[1].xo = 0;
    C[1].yo = 0;
    C[2].xo = fabs(C[2].xo);
    C[2].yo = fabs(C[2].yo);
    double t = C[2].R / sqrt(2) / 2;
    double xt = C[2].xo - t;
    double yt = C[2].yo - t; 
    // printf("%.6lf %.6lf\n", C[2].xo , C[2].yo);
    printf("%.6lf\n", xt + yt);
}

int main() {
    // ios::sync_with_stdio(false);
    int T; scanf("%d", &T);
    while (T--) {
        solve();
    }
    return 0;
}

gcf一顿积分，积出来了当点距离圆心为d时，欧几里得距离的平方的期望为r*r/2+d*d

所以如果圆心位于凸包内，直接输出r*r/2。否则枚举每条边，拿边上的点更新答案。如果点到直线距离位于线段内的话，用这个点到直线距离更好。

#include <bits/stdc++.h>

using namespace std;

const double PI = acos(-1), eps = 1e-8;
const int N = 5e3 + 9;
int n, q;
int sgn(double x) {
    return x <= -eps ? -1 : (x < eps ? 0 : 1);
}
struct Point {
    double x, y;
    Point() {}
    Point(double x, double y) : x(x), y(y) {}
    bool operator == (Point b) {
        return !sgn(x - b.x) &&!sgn(y - b.y);
    }
    Point operator + (Point b) {
        return {x + b.x, y + b.y};
    } 
    Point operator - (Point b) {
        return {x - b.x, y - b.y};
    }
    double operator * (Point b) {
        return x * b.x +y * b.y;
    }
    double operator ^ (Point b) {
        return x *b.y - y * b.x;
    }
    bool operator <(Point b) const {
        return sgn(x - b.x) == 0 ? sgn(y - b.y) < 0 : x < b.x;
    }
    double cross(Point b, Point c) {
        return (b - *this) ^ (c - *this);
    }
    double len() {return sqrt(x * x + y * y); }      
    double dis(Point p) {
        return (*this - p).len();
    }
    // void read() {
    //     scanf("%lf %lf", &x, &y);
    // }
} P[N];

struct Line {
    Point u, v;
    Line() {}
    Line(Point _u, Point _v) : u(_u), v(_v) {}
    double len() {
        return u.dis(v);
    }
    double cross(Point p) {
        return (v - u) ^ (p - u);
    }
    bool pointonseg(Point p) {
        return !sgn(cross(p)) && (p - u) * (p - v) <= 0;
    }
    double dispointtoline(Point p) {
        return fabs(cross(p)) / len();
    }
    double dispointtoseg(Point p) {
        if (sgn((p - u) * (v - u)) < 0 || sgn((p - v) * (u -  v)) <0)
            return min(p.dis(u), p.dis(v));
        return dispointtoline(p); 
    }
} ;

struct Pol {
    vector<Point> p;
    // void getconvex() {
    //     sort(p.begin(), p.end());
    // }
    vector<Line> l;
    void getline() {
        l.resize(p.size());
        for (int i = 0; i < l.size(); ++i) {
            l[i] = Line(p[i], p[(i + 1) % p.size()]);
        }
    }
    int relationpoint(Point q) {
        for (auto i : p) if (i == q) return 3;
        if (l.size() == 0) getline();
        for (auto i : l) if (i.pointonseg(q)) return 2;
        int cnt = 0;
        for (int i = 0; i < p.size(); ++i) {
            int j = (i + 1) % p.size();
            double k = p[j].cross(q, p[i]);
            int u = sgn(p[i].y - q.y);
            int v = sgn(p[j].y - q.y);
            // cout<<k<<endl;
            if (k > 0 && u < 0 && v >= 0) cnt++;
            if (k < 0 && v < 0 && u >= 0) cnt--;
        }
        return cnt != 0;
    }
} pol;

double dist(double x, double y, double _x, double _y) {
    return sqrt((x - _x) * (x - _x) + (y - _y) * (y - _y));
}

struct circle {
    int x1, x2, y1, y2;
    double R, xo, yo;
    

    void read() {
        scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
    }

    void init() {
        read();
        xo = (1.0 * x1 + x2) / 2;
        yo = (1.0 * y1 + y2) / 2;
        R = dist(x1, y1, x2, y2);
    }
} C[N];

double calc(double a, double y1) {
    return a * a / 2 + y1 * y1;
}

void solve(int i) {
    P[i] = Point(C[i].xo, C[i].yo);
    // cout << C[i].xo << " " << C[i].yo << " " << C[i].R <<'\n';
    // cout << pol.relationpoint(P[i]) << '\n';
    if (pol.relationpoint(P[i]) != 0) {
        printf("%.6lf\n", calc(C[i].R / 2, 0));
        return ;
    }

    double ans = 8e18; 
    for (int j = 0; j < n; ++j) {
        ans = min(ans, calc(C[i].R / 2, dist(C[i].xo, C[i].yo, pol.p[j].x, pol.p[j].y)));
        // cout << ans << '\n' ;
    }
    // cout 
    for (int j = 0; j < pol.l.size(); ++j) {
        double y1 = pol.l[j].dispointtoseg(P[i]);
        // cout << y1 << ' ';
        ans = min(ans, calc(C[i].R / 2, y1));
    }
    printf("%.6lf\n", ans);
}

int main() {
    // freopen("1.in", "r", stdin);
    scanf("%d %d", &n, &q);
    for (int i = 1; i <= n; ++i) {
        double x, y;
        scanf("%lf %lf", &x, &y);
        pol.p.push_back(Point(x, y));
    }
    // for(auto x:pol.p)
    // {
    //     cout<<x.x<<' '<<x.y<<endl;
    // }
    for (int i = 1; i <= q; ++i) {
        C[i].init();
        solve(i);
    }
    return 0;
}

不太清楚，队友写的

#include <bits/stdc++.h>
using namespace std;



int main() {
    ios::sync_with_stdio(false);
    int n, T;
    cin >> n >> T;
    int k = 2;
    for (int i = 1; i <= n; ++i) {
        int t;
        cin >>t;
        k = max(k, (t + T- 1) / T);
    }
    cout << k;
    return 0;
}

代码

网络

2023