icpc刷题记录

E. Exam Results

尺取法，理清思路很重要。
1.将各个人的分数从大到小排序。将每个值作为本次枚举的大值，往后枚举看都多少个满足要求的值。
2.枚举的大值条件是：必须大于等于每个人获取最低分的最大值。

#include 
#define endl '\n'
#define int long long

using namespace std;
const int N = 3e6+100;
int n,p,vis[N];
struct node
{
    int id,val;
}e[N];
bool cmp(node e1,node e2)
{
    return e1.val>e2.val;
}
signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int T;cin>>T;
    int g=0;
    while(T--)
    {
        g++;
        cin>>n>>p;
        for(int i=0;i<=n+5;i++)
            vis[i]=0,e[i].val=0,e[i].id=0;
        int mx=0;
        for(int i=1;i<=n;i++)
        {
            int a,b;cin>>a>>b;
            e[i]={i,a};e[n+i]={i,b};
            mx=max(mx,b);
        }
        n*=2;
        sort(e+1,e+n+1,cmp);
        int t=0,h=0,cnt=0,ans=0;
        for(int i=1;i<=n;i++)
        {
            if(e[i].val<mx) break;
            while(t<n&&e[t+1].val*100>=e[i].val*p)
            {
                t++;
                vis[e[t].id]++;
                if(vis[e[t].id]==1) cnt++;
            }
            ans=max(ans,cnt);
            vis[e[i].id]--;
            if(!vis[e[i].id]) cnt--;
        }
        cout<<"Case #"<<g<<": "<<ans<<endl;
    }
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

L. Clock Master

树上dp，求三个块内的点两两互相到达的距离。

#include 
#define int long long
#define endl '\n'

using namespace std;
const int N=7e5+5;
int n,sz[4][N],cnt[5];
double ans;
vector<pair<int,int>>e[N];
void dfs1(int u,int fa)
{
    for(auto x:e[u])
    {
        int v=x.first,w=x.second;
        if(v==fa) continue;
        dfs1(v,u);
        for(int i=1;i<=3;i++)
            sz[i][u]+=sz[i][v];
    }
}
void dfs2(int u,int fa)
{
    for(auto x:e[u])
    {
        int v=x.first,w=x.second;
        if(v==fa) continue;
        dfs2(v,u);
        for(int i=1;i<=3;i++)
        {
            for(int j=1;j<=3;j++)
            {
                if(i==j) continue;
                ans+=(sz[j][v]*1.0*(sz[i][1]-sz[i][v])*w/cnt[i]/cnt[j]/2);
            }
        }
    }
}
void solve()
{
    cin>>n;
    for(int i=1;i<n;i++)
    {
        int u,v,w;cin>>u>>v>>w;
        e[u].push_back({v,w});
        e[v].push_back({u,w});
    }
    for(int i=1;i<=3;i++)
    {
        cin>>cnt[i];
        for(int j=1;j<=cnt[i];j++)
        {
            int x;cin>>x;
            sz[i][x]++;
        }
    }
    dfs1(1,0);
    dfs2(1,0);
    cout<<fixed<<setprecision(9)<<ans<<endl;
}
signed main()
{
//    int T;cin>>T;
//    while(T--)
        solve();
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

Problem E

The League of Sequence Designers
思路：前n-2个数为0，后面2个未知数x,y,推公式得到的系数为L-1,L
直接转化为扩欧问题，找到一个y为负的一组解即可

#include 
#define endl '\n'
#define int long long
using namespace std;
const int inf=1e18;
const int N =2e6+6;
int k,L,p;
int ex_gcd(int a,int b,int &x,int &y)
{
    if(b==0)
    {
        x=1,y=0;return a;
    }
    int gcd=ex_gcd(b,a%b,y,x);
    y-=a/b*x;
    return gcd;
}
int Cal(int a,int b,int c)
{
    int x,y;
    int gcd=ex_gcd(a,b,x,y);
    if(c%gcd) return -1;
    x*=c/gcd;
    b/=gcd;
    if(b<0) b=-b;
    int ans=x%b;
    if(ans<=0) ans+=b;
    for(int i=ans;;i+=b)
    {
        int g=k-(L-1)*i;
        if(g<0&&g%b==0)
        {
            p=g/b;
            return i;
        }
    }
    return ans;
}
void solve()
{
    cin>>k>>L;
    if(L>=2000)
    {
        cout<<-1<<endl;return;
    }
    int x=Cal(L-1,L,k);
    cout<<L<<endl;
    for(int i=1;i<=L-2;i++)
        cout<<0<<" ";
    cout<<p<<" "<<x<<endl;

}
signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int T;cin>>T;
    while(T--)
        solve();
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

G. Greatest Common Divisor

好多特判啊，这题！！！ 麻了
注意点：
1.对于一个数来说，若不为1，则不需要进行进行加1操作，直接输出0；若正好是1个1，那么只需要加1即可。
2.开始讨论d的取值：
若差分后n-1项最大公约数为1，说明没有解，输出-1；
若为0，说明后n-1项都为0，说明数组中所有的数都相同，又回到是否为1的讨论。
3.之后要解决的问题：数组第一项x，后n-1的最大公约数d，对x进行加1的操作，使得gcd(x,d)不为1，暴力求出需要几次操作。

#include 
#define endl '\n'
#define int long long
#define ios ios::sync_with_stdio(false)
#pragma-GCC-optimize("-Ofast");
using namespace std;
const int N =1e6+5;
const int inf=1e18;
const int mod=1e9+7;
const double eps=1e-8;
int n,a[N],b[N],cnt;
void solve()
{
    cnt++;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    if(n==1&&a[1]!=1)
    {
        cout<<"Case "<<cnt<<": "<<0<<endl;return;
    }
    else if(n==1&&a[1]==1)
    {
        cout<<"Case "<<cnt<<": "<<1<<endl;return;
    }
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++) b[i]=a[i]-a[i-1];
    int d=0;
    for(int i=2;i<=n;i++)
        d=__gcd(b[i],d);
    if(d==1)
    {
        cout<<"Case "<<cnt<<": "<<-1<<endl;
        return;
    }
    else if(d==0)
    {
        if(a[1]==1)
            cout<<"Case "<<cnt<<": "<<1<<endl;
        else
            cout<<"Case "<<cnt<<": "<<0<<endl;
        return;
    }
    int x=a[1];
    if(__gcd(x,d)!=1)
    {
        cout<<"Case "<<cnt<<": "<<0<<endl;return;
    }
    vector<int>e;
    for(int i=1;i*i<=d;i++)
    {
        if(d%i==0)
            e.push_back(i);
        if(d%i==0&&d/i!=i)
            e.push_back(d/i);
    }
    int ans=inf;
    //cout<
    for(int y:e)
    {
        if(y==1) continue;
        int g=(x/y+1)*y-x;
        //cout<
        ans=min(ans,g);
    }
    cout<<"Case "<<cnt<<": "<<ans<<endl;return;
}
signed main()
{
    ios;
    int T;cin>>T;
    while(T--)
        solve();
    return 0;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

Average distance

将一个树中任意两个点权值累加。

#include 
#define int long long
#define endl '\n'

using namespace std;
const int N=7e5+5;
vector<pair<int,int>>e[N];
int n,sz[N];
double dp[N];
void dfs(int u,int fa)
{
    sz[u]=1;
    for(auto x:e[u])
    {
        int v=x.first,w=x.second;
        if(v==fa) continue;
        dfs(v,u);
        sz[u]+=sz[v];
        dp[u]+=(dp[v]+(sz[v]*1.0*(n-sz[v])*w));
    }
}
void solve()
{
    cin>>n;
    for(int i=0;i<=n+5;i++) e[i].clear(),dp[i]=0,sz[i]=0;
    for(int i=1;i<n;i++)
    {
        int u,v,w;cin>>u>>v>>w;
        e[u].push_back({v,w});
        e[v].push_back({u,w});
    }
    dfs(0,-1);
    int base=n*(n-1)/2;
    cout<<fixed<<setprecision(12)<<dp[0]/base<<endl;
}
signed main()
{
    int T;cin>>T;
    while(T--)
        solve();
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

K. Kingdom’s Power

本题的关键点应该是对于树上结点的操作，比如每个结点可到达的最大深度、上一次遍历路径的最长链的末端结点

#include 
#define endl '\n'
#define int long long
using namespace std;
const int N=2e6+5;
int n,dep[N],mx[N],pre[N],ans;
vector<int>e[N];
void dfs1(int u)
{
    for(int v:e[u])
    {
        dep[v]=dep[u]+1;
        mx[v]=dep[v];
        dfs1(v);
        mx[u]=max(mx[u],mx[v]); //每个结点可到达的最大深度
    }
}
void dfs2(int u)
{
    pre[u]=u;
    for(int v:e[u])
    {
        ans+=min(dep[v],dep[pre[u]]-dep[u]+1);  //上一次子节点所在的最长链末端t
        dfs2(v);
        pre[u]=pre[v];  //记录本次最长连的末端结点t
    }
}
bool cmp(int a,int b)
{
    return mx[a]<mx[b];
}
signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int cs=0;
    int T;cin>>T;
    while(T--)
    {
        cs++;
        cin>>n;
        for(int i=1;i<=n+5;i++)
            dep[i]=0,mx[i]=0,pre[i]=0,e[i].clear();
        for(int i=2;i<=n;i++)
        {
            int x;cin>>x;
            e[x].push_back(i);
        }
        dfs1(1);
        for(int i=1;i<=n;i++)
            sort(e[i].begin(),e[i].end(),cmp);
        ans=0;
        dfs2(1);
        cout<<"Case #"<<cs<<": "<<ans<<endl;
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57