ACM-ICPC 2018 南京赛区网络预赛

Diposting di | Edited on

传送门

A. An Olympian Math Problem

题意

求

S%n;

思路

A

所以直接输出N-1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
ll n;
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int t;
    cin>>t;
    while(t--){
        cin>>n;
        cout<<n-1<<endl;
    }
    return 0;
}

B. The writing on the wall

题意

一个n*m的方格矩阵,有的格子被涂成了黑色,问该矩阵中有多少个子矩阵,子矩阵不包含黑色格子;

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
#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<cmath>
using namespace std ;

#define clr( a , x ) memset ( a , x , sizeof a )


int U[100005] , S[100005] , cur , c[100005][105] , d[100005][105], n , m ,k,a,b,xxx;

void solve () {
    clr ( U , 0 ) ;
    clr(c,0);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            d[i][j]=1;
        }
    }
    cur=0;
    for(int i=0;i<k;i++){
        scanf("%d %d",&a,&b);
        d[a][b]=0;
    }
    for ( int i = 1 ; i <= n ; ++ i ) {
        for ( int j = 1 ; j <= m ; ++ j ) U[j] = d[i][j] == 1 ? U[j] + 1 : 0 ;
        cur = 0 ;
        S[++ cur] = 0 ;
        for ( int j = 1 ; j <= m + 1 ; ++ j ) {
            while ( U[j] < U[S[cur]] ) {
                c[max ( U[S[cur - 1]] , U[j] ) + 1][j - S[cur - 1] - 1] ++ ;
                c[U[S[cur]] + 1][j - S[cur - 1] - 1] -- ;
                -- cur ;
            }
            while ( cur >= 1 && U[j] == U[S[cur]] ) -- cur ;
            S[++ cur] = j ;
        }
    }
    for ( int i = 1 ; i <= n ; ++ i ) {
        for ( int j = 1 ; j <= m ; ++ j ) c[i][j] += c[i - 1][j] ;
    }
    for ( int i = 1 ; i <= n ; ++ i ) {
        for ( int j = m - 1 ; j >= 1 ; -- j ) c[i][j] += c[i][j + 1] ;
        for ( int j = m - 1 ; j >= 1 ; -- j ) c[i][j] += c[i][j + 1] ;
    }
    long long ans=0;
    for ( int i = 1 ; i <= n ; ++ i ) {
        for ( int j = 1 ; j <= m ; ++ j ) {
            ans+=c[i][j];
          //  printf ( "%d%c" , c[i][j] , j < m ? ' ' : '\n' ) ;
        }
    }
    printf("Case #%d: %lld\n",xxx++,ans);
}

int main () {

    int t;
    scanf("%d",&t);
    xxx=1;
    while(t--){
        scanf("%d %d %d",&n,&m,&k);
        solve () ;
    }

    return 0 ;
}

E. AC Challenge

题意

N道题目，每个题目有得分A和得分B还有K个前置题目,在答这题时必须要把前置题目都答了才行,每个题目答对的得分是A*答这题当前时间+得分B;

每道题会有前置的做题需求，给我们题目的价值表示方法，要我们求出做这些题目可以获得的做大价值。

思路

一开始以为是拓扑排序，后来看到只有二十道题目直接状态压缩枚举每道题是否答过。然后判断这个状态可否再答题每次比较最大值得出答案。

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1000000007;
const int maxn=(1<<21)+50;
const int MAXN=2e7+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
ll a[50];
ll b[50];
ll now[maxn];//状态
ll dp[maxn];//状态的得分
ll num[maxn];//里面有多少个1
ll ok[maxn];//记录这个需要的条件
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i]>>b[i];
        int k;
        cin>>k;
        for(int j=0;j<k;j++){
            int p;
            cin>>p;p--;
            ok[i]|=(1<<p);
        }
    }
    ll sum=0;
    memset(dp,-inf,sizeof(dp));
    dp[0]=0;
    for(ll i=0;i<(1<<n);i++){
        ll k=i;
        for(int j=0;j<=21;j++){
            if(i&(1<<j))num[i]++;
        }
        if(dp[i]==-inf)continue;//如果当前状态不可能;
        sum=max(sum,dp[i]);
        for(int j=0;j<n;j++){
            if((i&(1<<j)))continue;
            if((i&(ok[j]))!=ok[j])continue;
            dp[i|(1<<j)]=max(dp[i|(1<<j)],dp[i]+(num[i]+1)*a[j]+b[j]);
        }

    }
    cout<<sum<<endl;
    return 0;
}

G. Lpl and Energy-saving Lamps

题意

给N个房间换灯泡，城堡N个房间，每个月获得M个灯泡，然后每个房间按顺序走过去，如果手上灯泡数量大于等这个房间的灯泡数量,就把这个房间的灯泡数量替换,下一个从第一个房间开始;然后询问第Q个月换了几个房间还剩几个灯泡；

思路

线段树维护区间最小值，如果左子树的最小值比当前值大就不管右子树，然后询问到叶子节点，替换完后把最小值置为inf更新有关联的结点，然后从当前位置到N再询问一次,知道询问不出来或者已经到达N

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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1000000007;
const int maxn=1e5+50;
const int MAXN=2e7+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
const int inff=0x3f3f3f3f;
struct node{
    int id,l,r,val;
    int mi;
}my[maxn<<2];
int a[maxn];
int b[maxn];
void up(int i){
    if(my[i].l==my[i].r)return;
    if(a[my[i<<1].mi]<a[my[(i<<1)|1].mi])my[i].mi=my[i<<1].mi;
    else my[i].mi=my[(i<<1)|1].mi;
}
void build(int i,int l,int r){
    my[i].l=l;
    my[i].r=r;
    if(l==r){
        my[i].mi=my[i].val=l;
        b[l]=i;
        return;
    }
    int mid=(l+r)/2;
    build(i<<1,l,mid);
    build((i<<1)|1,mid+1,r);
    up(i);
}
int query(int i,int l,int r,int v){
    //cout<<"i=="<<i<<" "<<my[i].mi<<endl;
    if(a[my[i].mi]>v)return -1;
    if(my[i].l==my[i].r){
        if(a[my[i].mi]<=v)
        return my[i].mi;
        else return -1;
    }
    int mid=(my[i].l+my[i].r)/2;
    int ll=-1,rr=-1;
    if(l<=mid){
        ll=query(i<<1,l,mid,v);
    }
    if(ll!=-1)return ll;
    if(r>mid){
        rr=query((i<<1)|1,mid+1,r,v);
    }
    if(rr!=-1)return rr;
    return -1;
}
void update(int i){
    if(i==-1)return;
    a[i]=inff;
    int t=b[i];
    while(t){
        up(t);
        t/=2;
        up(t);
    }
}
int anw1[maxn],anw2[maxn];
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n,m;
    while(cin>>n>>m){
        for(int i=1;i<=n;i++){
            cin>>a[i];
        }
        build(1,1,n);
        int one;
        one=0;
        int v=0;
        for(int j=1;j<=100000;j++){
            v+=m;
            int now=1;
            while(true){
                int mi=query(1,now,n,v);
               // cout<<"j=="<<j<<"mi=="<<mi<<endl;
                if(mi==-1)break;
               // cout<<"j=="<<j<<endl;
               // cout<<"mi=="<<mi<<endl;
               // cout<<"v=="<<v<<endl;
                v-=a[mi];
                one++;
                update(mi);
                now=mi+1;
            }
            anw1[j]=one;
            anw2[j]=v;
        }
        int q;
        cin>>q;
        while(q--){
            int d;
            cin>>d;
            cout<<anw1[d]<<" "<<anw2[d]<<endl;
        }
    }
    return 0;
}

I. Skr

题意

给你一个数字字符串问你数字字符串里面本质不同的回文字符串的数字和是多少；

思路

比赛的时候不会回文树所以放弃了，后面知道有的大佬用了马拉车+hash过了这题，有点后悔。

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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<map>
using namespace std;
#define ULL unsigned long long
#define ll long long
const int maxn=4000000+40;
const int mod=1e9+7;
ULL P = 1313131;
ULL sqr[maxn/2],has[maxn/2],V[maxn];
ll ha[maxn/2],tmp[maxn/2];
int Laxt[maxn],Next[maxn],cnt=0;
 
const int MOD = 2000007;

bool _insert(ULL Now)
{
       int u=Now%MOD;
       for(int i=Laxt[u];i;i=Next[i]){
        if(V[i]==Now) return true;
       }
       Next[++cnt]=Laxt[u];
       Laxt[u]=cnt;
       V[cnt]=Now;
       return false;
}
ll ans=0;
void _hash(int x,int y){
    ULL Now=has[y]-has[x-1]*sqr[y-x+1];
    if(!_insert(Now))
    {
		ans+=((ha[y]-ha[x-1]*tmp[y-x+1]%mod)%mod+mod)%mod;
		ans%=mod;
	}
} 
int r[maxn];
char c[maxn];
void _malacher()
{
    int R=0,Mid=0,Len;
    
    scanf("%s",c+1);
    Len=strlen(c+1);
    sqr[0]=tmp[0]=1;
    has[0]=ha[0]=0;
    for(int i=1;i<=Len;i++){
        sqr[i]=sqr[i-1]*P;
        has[i]=has[i-1]*P+c[i];
        tmp[i]=tmp[i-1]*10%mod;
        ha[i]=(ha[i-1]*10+c[i]-'0')%mod;
    }  
    
     for(int i=1;i<=Len;++i) {      
        _hash(i,i);
        if(R>i) r[i]=min(r[2*Mid-i],R-i);
        while(i+r[i]+1<=Len&&c[i+r[i]+1]==c[i-r[i]-1]){
            _hash(i-r[i]-1,i+r[i]+1);
            r[i]++;
        }
        if(i+r[i]>R) {
            R=i+r[i];
            Mid=i;
        }
    }
    
    cnt=0;Mid=0;R=0;
    memset(Laxt,0,sizeof(Laxt));
    memset(r,0,sizeof(r));
    for(int i=2;i<=Len;++i) {
        if(R>i) r[i]=min(r[2*Mid-i],R-i+1);
        while(i+r[i]<=Len&&c[i+r[i]]==c[i-r[i]-1]) {
            _hash(i-r[i]-1,i+r[i]);
            ++r[i];
        }
        if(i+r[i]-1>R) {
            R=i+r[i]-1;
            Mid=i;
        }
    }
    printf("%lld\n",ans);
}
int main()
{
    _malacher();
    return 0;
}

J. Sum

题意

一个数可以拆成两个因子,比如

但是也有的会拆成因子中有平方数的比如；12=2²×3，这样就不是题目需要的答案，

对于6我们可以拆成4个满足题目需求的分解例如 6=1×6=6×1=2×3=3×2总共有四种所以定义F(6)=4

现在要求求

思路

1.首先我们肯定知道素数只有1和自己两个因子所以素数就只有2,F(素数)=2；

2.如果不是素数那就肯定是由两个素数组成而来的,比如12(12=2²×3)是由2和3这两个素数得来的，但是如果12=4×3中间的4就是一个平方数所以不符合条件，但是4可以拿出一个2给3变成12=2×6这样就符合题目的条件

2.如果里面有一个素数的次方超过2比如

这里的2就算拿出一个给3也会变成4×6;这样4也是一个平方数;如果是2×12,这里这里的12里面包含一个平方数4也不行,所以超过3的数F(x)=0；

所以我们可以把一个数拆成无数个不同素数的各种方的乘积。

如果存在一个方超过2答案F(x)=0；

如果等于2说明他必须拆开,分布在两个因子中,所以贡献是1 就等于这是铁定的不能变的，

如果等于1说明他可以选和不选,所以贡献为2

所以就判断一个数的它因子的一次方是多少然后就这个数量的2次幂

最多的可能肯定是这个数的最小素数因子，然后判断答案是否有这个因子的二次方以上，如果是就为0，如果是2就忽略看其他的因子，如果是1就贡献2再看其他的因子；

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1000000007;
const int maxn=2e7+50;
const int MAXN=2e7+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
ll n;
ll a[maxn];
int prime[maxn];
int minprime[maxn];
int sum[maxn];
void get(){
    for(int i=0;i<MAXN;i++)prime[i]=0;
    for(int i=2;i<=MAXN;i++){
        if(!prime[i]){
            prime[++prime[0]]=i;
            minprime[i]=i;
        }
        for(int j=1;j<=prime[0]&&prime[j]<=MAXN/i;j++){
            prime[prime[j]*i]=1;
            minprime[prime[j]*i]=prime[j];
            if(i%prime[j]==0)break;
        }
    }
}

int main()
{
   // std::ios::sync_with_stdio(false);
    //std::cin.tie(0);
    //std::cout.tie(0);
    int t;
    get();
    a[1]=1;
    for(int i=2;i<=MAXN;i++){
        int M=minprime[i];
        if(ll(M*M)<MAXN&&ll(M*M*M)<MAXN&&i%(M*M*M)==0)
            a[i]=0;
        else if((ll)M*M<maxn&&i%(M*M)==0)
            a[i]=a[((i/M)/M)];
        else a[i]=2*a[i/M];
    }
    for(int i=1;i<MAXN;i++){
        sum[i]=sum[i-1]+a[i];
    }
    scanf("%d",&t);
    while(t--){
        int n;
        scanf("%d",&n);
        printf("%d\n",sum[n]);
    }
    return 0;
}

L. Magical Girl Haze

题意

单源最短路，但是可以有最多K个免费的道路，然你求从1到N的最短距离;

思路

这题不是我写的,但是我赛后研究了一下解法,应该是把每个路都加上一层K的免费路线，这种解法叫做分层图,这类题都有一个特征就是把某些边变为0，或者是变为一个其他的数，我们只要把这个图拓展成K层。原来的一条边扩展成与下一层的一条边，这样再跑最短路算法就可以了。然后遍历每层你要到的那个终点选出最小的一个就可以了。

不过注意总的最大边数是 复杂度应该是O（K×E×logE)

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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include<bits/stdc++.h>
using namespace std;
int s,t,n,m,k;
long long d[100000+10][11];
const long long INF=0x3f3f3f3f3f3f3f3f;
typedef pair<int,int> pii;
vector<pii> G[100000+10];
bool visit[100000+10][11];
struct Node
{
    int id;
    int level;
    int dis;
    Node(int id,int level,int dis):id(id),level(level),dis(dis)
    {

    }
    bool operator <(const Node& X)const
    {
        return dis>X.dis;
    }
};

int main()
{

    int a,b,c,j;
    int T;
    scanf("%d",&T);
    while(T--){
        cin>>n>>m>>k;
        s=1,t=n;
        priority_queue<Node> pq;
        for(int i=0;i<=n+1;i++){
            for(int j=0;j<=10;j++){
                d[i][j]=INF;
            }
        }
        for(int i=0;i<n;i++)
            G[i].clear();
        for(int i=0;i<m;i++)
        {
            scanf("%d%d%d",&a,&b,&c);
            for(j=0;j<G[a].size();j++){
                if(G[a][j].first==b){
                    if(G[a][j].second>c){
                        G[a][j].second=c;
                    }
                    break;
                }
            }
            if(j==G[a].size())
                G[a].push_back(make_pair(b,c));
        }
        memset(visit,0,sizeof(visit));
        for(int i=0;i<n;i++)
            for(int j=0;j<=k;j++)
                d[i][j]=INF;
        d[s][0]=0;
        pq.push(Node(s,0,0));
        while(!pq.empty())
        {
            Node X=pq.top();
            pq.pop();
            int x=X.id;
            int lv=X.level;
            if(visit[x][lv]==true)
                continue;
            else
            {
                visit[x][lv]=true;
                vector<pii>::iterator it;
                for(it=G[x].begin();it!=G[x].end();it++)
                {
                    int y=(*it).first;
                    int u=(*it).second;
                    if(u+d[x][lv]<d[y][lv])//同一层
                    {

                        d[y][lv]=u+d[x][lv];
                        pq.push(Node(y,lv,d[y][lv]));
                    }
                    if(lv<k)
                        if(d[x][lv]<d[y][lv+1])//不同层
                        {
                            d[y][lv+1]=d[x][lv];
                            pq.push(Node(y,lv+1,d[y][lv+1]));
                        }
                }
            }
        }
        long long ans=d[t][0];
        for(int i=0;i<=k;i++)
        {
            ans=min(ans,d[t][i]);
        }
        cout<<ans<<endl;
    }
    return 0;
}