2020.4.6--UCF Local Programming Contest 2017的正式赛

Problem A : Electric Bill

题目大意：进行电量分级制收费，1000kwh及以下一档收费，1000kwh以上按另一档收费，给出每个人的电量总额，问每人应支付多少钱。

思路：基础if else题，对于每个电量判断是否大于1000，再分别计算≤1000的价格和＞1000的价格，最后相加并输出。

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

#include<string>

#include<cmath>

#include<map>

#include<queue>

#include<set>

#include<stack>

#include<vector>

#include<complex>

#include<unordered_map>

#define deg(x) cout<<#x<<"="<<x<<endl;

#define fd(x) for(int i=0;i<x;i++)

#define fdd(a,x) for(int i=a;i<x;i++)

#define fx(x,n) for(int i=n-1;i>=x;i--)

#define mst(x) memset(x,0,sizeof(x));

#define fi first

#define se second

#define TB ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);

#define ok "ok"

#define HH puts("");

#define ls rt<<1

#define rs rt<<1|1

#define pb(a,b) a.push_back(b);

#define FIN  freopen("1.in","r",stdin);

#define FOUT freopen("1.out","w",stdout);

using namespace std;

typedef long long ll;

typedef pair<int,int> pii;

typedef pair<int,string> pss;

typedef unsigned long long ull;

const ll mod=1e18;

const ll inf=1e9;

const double eps=1e-8;

const double pi=acos(-1);

int main(){

    TB

    int n,m;

    cin>>n>>m;

    int t;

    cin>>t;

    while(t--){

        int k,sum=0;

        cin>>k;

        sum=n*min(k,1000);

        if(k>1000){

            sum+=m*(k-1000);

        }

        cout<<k<<" "<<sum<<'\n';

    }

    return 0;

}

Problem B : Simplified Keyboard

题目大意：给出一个字母分布图，如果两个字符串对应位置的字母全都相等，字符串属性为1，否则若两个字符串对应位置字母均相邻或相等，字符串属性为2，否则字符串属性为3. 现给出两个字符串，问这两个字符串的属性。

思路：可以先预处理每个字母的相邻关系，然后若a字符串与b字符串长度不等则属性必为3。长度相等时，遍历ab字符串并比较对应位置，并记录相等的数量及相邻的数量，最后判断输出。

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

#include<string>

#include<cmath>

#include<map>

#include<queue>

#include<set>

#include<stack>

#include<vector>

#include<complex>

#include<unordered_map>

#define deg(x) cout<<#x<<"="<<x<<endl;

#define fd(x) for(int i=0;i<x;i++)

#define fdd(a,x) for(int i=a;i<x;i++)

#define fx(x,n) for(int i=n-1;i>=x;i--)

#define mst(x) memset(x,0,sizeof(x));

#define fi first

#define se second

#define TB ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);

#define ok "ok"

#define HH puts("");

#define ls rt<<1

#define rs rt<<1|1

#define pb(a,b) a.push_back(b);

#define FIN  freopen("1.in","r",stdin);

#define FOUT freopen("1.out","w",stdout);

using namespace std;

typedef long long ll;

typedef pair<int,int> pii;

typedef pair<int,string> pss;

typedef unsigned long long ull;

const ll mod=1e18;

const ll inf=1e9;

const double eps=1e-8;

const double pi=acos(-1);

char a[5][20]={"","abcdefghi","jklmnopqr","stuvwxyz"};

bool f[203][203];

int fun(int x,int y,int q,int p){

    f[a[x][y]][a[q][p]]=f[a[q][p]][a[x][y]]=1;

    return 0;

}

int fun1(int x,int y){

    if(!a[x][y]) return 0;

    if(a[x][y+1]) fun(x,y,x,y+1);

    if(a[x][y-1]) fun(x,y,x,y-1);

    if(a[x+1][y+1]) fun(x,y,x+1,y+1);

    if(a[x+1][y-1]) fun(x,y,x+1,y-1);

    if(a[x+1][y]) fun(x,y,x+1,y);

    if(a[x-1][y]) fun(x,y,x-1,y);

    if(a[x-1][y+1]) fun(x,y,x-1,y+1);

    if(a[x-1][y-1]) fun(x,y,x-1,y-1);

    return 0;

}

int main(){

    TB

    mst(f)

    fdd(1,4) for(int j=0;j<9;j++) fun1(i,j);

    int t;

    cin>>t;

    while(t--){

        string s,b;

        cin>>s>>b;

        if(s.length()!=b.length()){

            cout<<3<<'\n';

            continue;

        }

        int flag=0,flag1=0;

        fd(s.length()){

            if(s[i]==b[i]) flag++,flag1++;

            else if(f[s[i]][b[i]]) flag1++;

        }

        if(flag==s.length()) cout<<1<<'\n';

        else if(flag1==s.length()) cout<<2<<'\n';

        else cout<<3<<'\n';

    }

    return 0;

}

Problem C : Singin' in the Rain

题目大意：给出一个歌单顺序，每次听完上一首歌后需要通过按上一曲或下一曲直至达到下一首要听的歌，问要听完整个给出的歌单顺序，需要按多少次按钮，

思路：由于每次都必须达到并听完某首歌后，才能去听下一首歌单里的歌，所以每次的转换是互不影响的，所以只需用两个函数分别计算从当前歌跳至下一首目标歌曲时，往前跳和往后跳所需次数，取min记录，最后求和即是答案。需注意每次开始跳跃时是听完上一首歌，即是从上一首歌+1的位置开始跳跃。

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

#include<string>

#include<cmath>

#include<map>

#include<queue>

#include<set>

#include<stack>

#include<vector>

#include<complex>

#include<unordered_map>

#define deg(x) cout<<#x<<"="<<x<<endl;

#define fd(x) for(int i=0;i<x;i++)

#define fdd(a,x) for(int i=a;i<x;i++)

#define fx(x,n) for(int i=n-1;i>=x;i--)

#define mst(x) memset(x,0,sizeof(x));

#define fi first

#define se second

#define TB ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);

#define ok "ok"

#define HH puts("");

#define ls rt<<1

#define rs rt<<1|1

#define pb(a,b) a.push_back(b);

#define FIN  freopen("1.in","r",stdin);

#define FOUT freopen("1.out","w",stdout);

using namespace std;

typedef long long ll;

typedef pair<int,int> pii;

typedef pair<int,string> pss;

typedef unsigned long long ull;

const ll mod=1e18;

const ll inf=1e9;

const double eps=1e-8;

const double pi=acos(-1);

int n,m;

ll down(ll x,ll y){

    x=x+1;

    if(x<=y) return y-x;

    y+=n;

    return y-x;

}

ll up(ll x,ll y){

    x=x+1;

    if(y<=x) return x-y;

    x+=n;

    return x-y;

}

int main(){

    TB

    int t;

    cin>>t;

    while(t--){

        cin>>n>>m;

        ll f,g;

        cin>>f;

        ll sum=0;

        while(--m){

            cin>>g;

            sum+=min(up(f,g),down(f,g));

            //deg(sum)

            f=g;

        }

        cout<<sum<<'\n';

    }

    return 0;

}

Problem D : Editor Navigation

题目大意：给出一个文档里的当前光标位置，和目标位置，光标移动规则按word的移动规则，问最少需要按多少次按键才可到达目标位置。

思路：从当前点出发进行bfs，直到达到目标位置停下。bfs时进行上下左右四次移动，且根据特殊规则判断落点应在何处。

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

#include<string>

#include<cmath>

#include<map>

#include<queue>

#include<set>

#include<stack>

#include<vector>

#include<complex>

#include<unordered_map>

#define deg(x) cout<<#x<<"="<<x<<endl;

#define fd(x) for(int i=0;i<x;i++)

#define fdd(a,x) for(int i=a;i<x;i++)

#define fx(x,n) for(int i=n-1;i>=x;i--)

#define mst(x) memset(x,0,sizeof(x));

#define fi first

#define se second

#define TB ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);

#define ok "ok"

#define HH puts("");

#define ls rt<<1

#define rs rt<<1|1

#define pb(a,b) a.push_back(b);

#define FIN  freopen("1.in","r",stdin);

#define FOUT freopen("1.out","w",stdout);

using namespace std;

typedef long long ll;

typedef pair<int,int> pii;

typedef pair<int,string> pss;

typedef unsigned long long ull;

const ll mod=1e18;

const ll inf=1e9;

const double eps=1e-8;

const double pi=acos(-1);

int dx[]={0,0,1,-1},dy[]={1,-1,0,0};

int ans[125][85],s[125];

queue<pii> que;

int f;

int main(){

    TB

    int t;

    cin>>t;

    while(t--){

        cin>>f;

        for(int i=1;i<=f;i++) cin>>s[i];

        for(int i=1;i<=f;i++) fill(ans[i],ans[i]+81,inf);

        int sx,sy,ex,ey;

        cin>>sx>>sy>>ex>>ey;

        que.push(pii(sx,sy));

        ans[sx][sy]=0;

        while(!que.empty()){

            int x=que.front().fi,y=que.front().se;que.pop();

            for(int i=0;i<4;i++){

                int nx=dx[i]+x,ny=dy[i]+y;

                if(nx<1||nx>f)continue;

                if(i==0&&ny>s[x]){ nx++;ny=0; }

                else if(i==1&&ny<0){ nx--;ny=s[nx]; }

                else if((i==2||i==3)&&ny>s[nx])ny=s[nx];

                if(nx<1||nx>f)continue;

                if(ans[nx][ny]!=inf)continue;

                ans[nx][ny]=ans[x][y]+1;

                que.push(pii(nx,ny));

            }

        }

        cout<<ans[ex][ey]<<'\n';

    }

    return 0;

}

Problem E: Simple Darts

题目大意：现给出一个圆形飞镖靶，分成等大小的w块扇形，且每个扇形分为3部分，半径为b以内的是靶心，半径在b到d之间的为双倍区，半径在d到s之间的为单倍区。现给出每次飞镖的落点，问最终总得分是多少。

思路：用自带函数atan或acos即可判断出落点与x轴的夹角，并可通过夹角判断出是在哪一片扇形，然后计算出落点离圆心的距离判断是靶心，双倍，单倍或靶外，最后把得分相加即可。

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

#include<string>

#include<cmath>

#include<map>

#include<queue>

#include<set>

#include<stack>

#include<vector>

#include<complex>

#include<unordered_map>

#define deg(x) cout<<#x<<"="<<x<<endl;

#define fd(x) for(int i=0;i<x;i++)

#define fdd(a,x) for(int i=a;i<x;i++)

#define fx(x,n) for(int i=n-1;i>=x;i--)

#define mst(x) memset(x,0,sizeof(x));

#define fi first

#define se second

#define TB ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);

#define ok "ok"

#define HH puts("");

#define ls rt<<1

#define rs rt<<1|1

#define pb(a,b) a.push_back(b);

#define FIN  freopen("1.in","r",stdin);

#define FOUT freopen("1.out","w",stdout);

using namespace std;

typedef long long ll;

typedef pair<int,int> pii;

typedef pair<string,string> pss;

typedef unsigned long long ull;

const ll mod=1e18;

const ll inf=1e9;

const double eps=1e-8;

const double pi=acos(-1);

int main(){

    TB

    int t;

    cin>>t;

    while(t--){

        double w,b,d,s;

        cin>>w>>b>>d>>s;

        int sum=0,n,flag;

        cin>>n;

        double x,y,tmp=2.0/w,ans,tmp1;

        while(n--){

            cin>>x>>y;

            double len=sqrt(x*x+y*y);

            if(len-b<eps){

                sum+=50;

            }else if(len-s>eps){

                sum+=0;

            }else{

                if(x==0){

                    if(y<0) ans=1.5;

                    else ans=0.5;

                }else{

                    ans=y/x;

                    ans=atan(ans)/pi;

                    if(ans<0) ans=1.0+ans;

                    if(y<0) ans+=1.0;

                }

                flag=1;tmp1=tmp;

                while(ans-tmp1>eps){

                    tmp1+=tmp;flag++;

                }

                if(len-d<eps) flag*=2;

                sum+=flag;

            }

        }

        cout<<sum<<'\n';

    }

    return 0;

}

Problem F: Multimodal Transport

每个城市转换交通方式的费用可以看做是走了一条对应费用的边，于是可以以每个城市在每种交通方式的状态为节点建图，同城市间的点之间连一条费用为转换费用的边，再将其它边相连后求最短路就是答案

#include <bits/stdc++.h>

using namespace std;

#define io ios::sync_with_stdio(false)

#define pb push_back

#define pqueue priority_queue

#define fi first

#define se second

#define ls rt<<1

#define rs rt<<1|1

#define sz(x) (int)(x).size()

#define dbg(x) cout<<#x<<" --- "<<x<<endl

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

#define fin(a) freopen(a,"r",stdin)

#define fout(a) freopen(a,"w",stdout)

typedef long long ll;

typedef pair<int,int> pii;

typedef pair<ll,ll> pll;

ll gcd(ll a,ll b){ return b==0?a:gcd(b,a%b); }

ll qpow(ll a,ll b,ll m){ ll r=1;a%=m;for(;b;b>>=1){if(b&1)r=r*a%m;a=a*a%m;}return r; }

const int inf=0x7fffffff;

const int maxn=2e3+10;

pqueue<pii,vector<pii>,greater<pii> > que;

map<string,int> mp[5],id;

vector<pii> g[maxn];

int d[maxn];

int n,m;

void dij(){

    for(int i=0;i<=4*n+1;i++)d[i]=inf;

    d[0]=0;que.push(pii(0,0));

    while(!que.empty()){

        int u=que.top().se,dis=que.top().fi;que.pop();

        if(d[u]<dis)continue;

        for(pii x:g[u]){

            int v=x.fi,c=x.se;

            if(d[v]>d[u]+c){

                d[v]=d[u]+c;

                que.push(pii(d[v],v));

            }

        }

    }

}

int main(){

    io;

    id["BOAT"]=0;id["RAIL"]=1;id["AIR"]=2;id["TRUCK"]=3;

    int T;cin>>T;

    while(T--){

        cin>>n;

        for(int i=0;i<4;i++)mp[i].clear();

        for(int i=0;i<=4*n+1;i++)g[i].clear();

        int tot=0;

        for(int i=1;i<=n;i++){

            int c;string s;cin>>s>>c;

            for(int j=0;j<4;j++)mp[j][s]=++tot;

            for(int j=0;j<4;j++)

                for(int k=0;k<4;k++)

                    if(j!=k)g[mp[j][s]].pb(pii(mp[k][s],c));

        }

        cin>>m;

        while(m--){

            int c;string u,v,f;cin>>u>>v>>f>>c;

            int ff=id[f];

            g[mp[ff][u]].pb(pii(mp[ff][v],c));

            g[mp[ff][v]].pb(pii(mp[ff][u],c));

        }

        string s,t;cin>>s>>t;

        for(int i=0;i<4;i++)g[0].pb(pii(mp[i][s],0));

        for(int i=0;i<4;i++)g[mp[i][t]].pb(pii(4*n+1,0));

        dij();

        cout<<d[4*n+1]<<endl;

    }

    return 0;

}

/**

2

4

ORLANDO 10

TAMPA 15

MIAMI 5

JACKSONVILLE 10

7

TAMPA JACKSONVILLE AIR 100

MIAMI TAMPA SEA 70

JACKSONVILLE MIAMI RAIL 45

ORLANDO JACKSONVILLE TRUCK 85

TAMPA ORLANDO RAIL 10

MIAMI JACKSONVILLE SEA 15

ORLANDO MIAMI TRUCK 15

JACKSONVILLE TAMPA

2

ORLANDO 15

TAMPA 10

3

ORLANDO TAMPA AIR 7

TAMPA ORLANDO TRUCK 3

ORLANDO TAMPA RAIL 19

ORLANDO TAMPA

*/

Problem G: Videogame Probability

由于数据较小，于是可以c1+…+cn个物品作为单个的处理，dp[i][j]表示，前i个全部拿到需要j次尝试的概率，p[i]为第i个物品的掉落几率，cnt为总数量

dp[i][j]+=dp[i-1][j-1]*p[i]

dp[i-1][j]+=dp[i-1][j-1]*(1.0-p[i])

最后dp[cnt][j]的和就是答案

#include <bits/stdc++.h>

using namespace std;

#define io ios::sync_with_stdio(false)

#define pb push_back

#define pqueue priority_queue

#define fi first

#define se second

#define ls rt<<1

#define rs rt<<1|1

#define sz(x) (int)(x).size()

#define dbg(x) cout<<#x<<" --- "<<x<<endl

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

#define fin(a) freopen(a,"r",stdin)

#define fout(a) freopen(a,"w",stdout)

typedef long long ll;

typedef pair<int,int> pii;

typedef pair<ll,ll> pll;

ll gcd(ll a,ll b){ return b==0?a:gcd(b,a%b); }

ll qpow(ll a,ll b,ll m){ ll r=1;a%=m;for(;b;b>>=1){if(b&1)r=r*a%m;a=a*a%m;}return r; }

const int inf=0x7fffffff;

double p[55],dp[3000][10005];

vector<double> ve;

int c[55];

int n,a;

int main(){

    int T;cin>>T;

    while(T--){

        scanf("%d",&n);

        ve.clear();ve.pb(0);

        for(int i=1;i<=n;i++)scanf("%d%lf",&c[i],&p[i]);

        for(int i=1;i<=n;i++)while(c[i]--)ve.pb(p[i]);

        scanf("%d",&a);

        for(int i=0;i<sz(ve);i++)

            for(int j=0;j<=a;j++)

                dp[i][j]=0;

        dp[0][0]=1;

        for(int i=1;i<sz(ve);i++)

            for(int j=1;j<=a;j++){

                dp[i][j]+=dp[i-1][j-1]*ve[i];

                dp[i-1][j]+=dp[i-1][j-1]*(1.0-ve[i]);

            }

        double ans=0;

        for(int i=0;i<=a;i++)ans+=dp[sz(ve)-1][i];

        printf("%.3lf\n",ans);

    }

    return 0;

}

Problem H: Maximum Non-Overlapping Increasing Subsequences

首先暴力预处理出每个区间的lis长度，然后对于1-n每个长度区间dp即可，时间复杂度o(n4)

#include <bits/stdc++.h>

using namespace std;

#define io ios::sync_with_stdio(false)

#define pb push_back

#define pqueue priority_queue

#define fi first

#define se second

#define ls rt<<1

#define rs rt<<1|1

#define sz(x) (int)(x).size()

#define dbg(x) cout<<#x<<" --- "<<x<<endl

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

#define fin(a) freopen(a,"r",stdin)

#define fout(a) freopen(a,"w",stdout)

typedef long long ll;

typedef pair<int,int> pii;

typedef pair<ll,ll> pll;

ll gcd(ll a,ll b){ return b==0?a:gcd(b,a%b); }

ll qpow(ll a,ll b,ll m){ ll r=1;a%=m;for(;b;b>>=1){if(b&1)r=r*a%m;a=a*a%m;}return r; }

const int inf=0x7fffffff;

int dp[105][105][105];

int cnt[105][105];

int a[105],b[105];

int n;

int lis(int l,int r){

    int len=0;

    for(int i=l;i<=r;i++){

        if(b[len]<a[i])b[++len]=a[i];

        else {

            int p=lower_bound(b+1,b+1+len,a[i])-b;

            b[p]=a[i];

        }

    }

    return len;

}

int main(){

    b[0]=-inf;

    int T;cin>>T;

    while(T--){

        scanf("%d",&n);

        for(int i=1;i<=n;i++)scanf("%d",&a[i]);

        for(int i=1;i<=n;i++)

            for(int j=i;j<=n;j++)

                cnt[i][j]=lis(i,j);

        mst(dp,0);

        for(int i=1;i<=n;i++)dp[1][i][i]=1;

        for(int kk=1;kk<=cnt[1][n];kk++){

            for(int len=2;len<=n;len++){

                for(int i=1;i<=n;i++){

                    int j=i+len-1;

                    if(j>n)break;

                    if(cnt[i][j]>=kk)dp[kk][i][j]=cnt[i][j];

                    for(int k=i;k<j;k++){

                        dp[kk][i][j]=max(dp[kk][i][j],dp[kk][i][k]+dp[kk][k+1][j]);

                    }

                }

            }

        }

        for(int i=1;i<=n;i++){

            if(i-1)printf(" ");

            printf("%d",dp[i][1][n]);

        }

        puts("");

    }

    return 0;

}

/**

3

8

2 1 9 3 4 4 5 6

2

1 1

3

1 2 3

*/

Problem I :Rotating Cards

有一堆数字1~n的卡片，你需要按照数字1~n的顺序将他们删去。你只能删去最上面的那张卡片，但你可以将最上面的卡片移动到最底部，也可以将最底部的卡片移动到最上面，问移动次数最少是多少。

很显然，想删去一张卡片，要么把它上面的所有卡片移动到底部，要么从底部将它拿上来。如果将这堆卡片的最上面和底部看作是首尾相连的，那么不管怎么移动，所有卡片的相对位置都是不变的。

用线段树或树状数组，区间查询，单点修改。对于删去第k张卡片，这个时候是第k-1张卡片在顶部。区间查询两张卡片之间剩余的卡片数量，就是将第k张卡片从上或从下（取决于这两张卡片一开始的相对位置）移动到顶部的移动次数a，n-k-a就是另一种移动方式的代价，取较小的那个。然后单点修改删去这张牌。

#include <cstdio>

long long pi[262145],pp[233333];

void shu(int k,int l,int r)

{

    if(l==r)

    {

        scanf("%lld",&pi[k]);

        pp[pi[k]]=l; return;

    }

    int i=k<<1,m=(l+r)>>1;

    shu(i,l,m); shu(i+1,m+1,r);

    pi[k]=pi[i]+pi[i+1];

    return;

}

long long cha(int k,int l,int r,int a,int b)

{

    if(l==a&&r==b) return pi[k];

    int i=k<<1,m=(l+r)>>1;

    if(a>m) return cha(i+1,m+1,r,a,b);

    else if(b<=m) return cha(i,l,m,a,b);

    else return cha(i,l,m,a,m)+cha(i+1,m+1,r,m+1,b);

}

void gai(int k,int l,int r,int x)

{

    if(l==r)

    {

        pi[k]=0; return;

    }

    int i=k<<1,m=(l+r)>>1;

    if(x>m) gai(i+1,m+1,r,x);

    else gai(i,l,m,x);

    pi[k]=pi[i]+pi[i+1];

    return;

}

int main()

{

    int t; scanf("%d",&t);

    while(t--)

    {

        int n; scanf("%d",&n);

        shu(1,1,n);

        long long sum=0,s=pi[1];

        for(int i=1,p=n; i<=n; i++)

        {

            long long t;

            if(p<pp[i]) t=cha(1,1,n,p,pp[i]-1);

            else t=cha(1,1,n,pp[i],p);

            if(t*2>s) sum+=s-t;

            else sum+=t;

            s-=i; gai(1,1,n,pp[i]); p=pp[i];

        }

        printf("%lld\n",sum);

    }

    return 0;

}

Problem J :Multiples

求1~b中有多少数字是2~a的倍数。

只取2~a中的质数，用容斥原理解决。

对于质数k1,k2，1~b中能整除他们的数的数量分别为b/k1,b/k2。但其中有些数被重复运算，再减去b/(k1*k2)，则是1~b中能整除k1或k2的数字的个数。

对于n个质数也是一样的做法。加上b除以各个质数，减去b除以任选两个质数的积，加上b除以任选三个质数的积……

求这些质数的积可以用dp来求。

#include <cstdio>

int pi[233],pl[233];

long long pp[33333333];

bool pf[233],ff[33333333];

int main()

{

    for(int i=3; i<=130; i+=2)

    {

        if(pf[i]==false) pi[++pi[0]]=i;

        for(int j=1; j<=pi[0]; j++)

        {

            if(i*pi[j]>130) break;

            pf[i*pi[j]]=true;

            if(i%pi[j]==0) break;

        }

    }

    pp[++pp[0]]=1; pl[0]=1;

    for(int i=1; i<=pi[0]; i++)

    {

        for(int j=1; j<=pl[i-1]; j++) if(pp[j]*pi[i]<(long long)1000000000000001)

        {

            pp[++pp[0]]=pp[j]*pi[i];

            ff[pp[0]]=not ff[j];

        }

        pl[i]=pp[0];

    }

    int t; scanf("%d",&t);

    while(t--)

    {

        int k; long long n,sum;

        scanf("%d%lld",&k,&n); sum=n/2;

        for(int i=1; i<=pi[0]; i++) if(pi[i]>k) break;

        else for(int j=pl[i-1]+1; j<=pl[i]; j++) if(pp[j]<=n)

        {

            long long p=(n/pp[j]+1)/2;

            if(ff[j]==true) sum+=p;

            else sum-=p;

        }

        printf("%lld\n",sum);

    }

    return 0;

}

Problem K :K-Item Shopping Spree

有n件商品，每件商品有自己的编号和价格，且每件商品的数量是无限的。问买恰好k件商品，并且价格恰好是t的购买方案数。只要编号顺序不同就认为是不同的。

首先就能想到的dp是，枚举商品数k，t2更新，维护出f[k][t]表示k件商品价格为t的方案数。但显然是超时的。

第一个很容易想到的优化，如果我们有了f[k/2][t]，那么就可以直接算出f[k][t]，不必一个一个枚举，这样就是n2logt，但还是不行。

还有的优化就是fft的优化。fft的原理和代码网上有很多讲得好的教程，在这里就不多讲了，我只说一下fft在这里应该怎么使用。

两个一元n次多项式相乘，朴素的方法需要n2的时间，而fft只需要nlogn。

在这题中，将方案数看作是系数，将价格看作是次方。这样更新的过程就可以看作是两个一元多次的多项式相乘。比如有a种方案价格x，b种方案价格y，两者更新后就是a*b种方案价格x+y，就像是两个数字相乘。

所以最后时间复杂度为nlognlogt。关于空间的优化，第一维的k是可以去掉的。

// Arup Guha

// 8/22/2017

// Solution to 2017 UCF Locals Problem: K Shop

#include <iostream>

#include <cmath>

using namespace std;

// Constants

const double PI = 3.14159265358979;

const long long MOD = 997LL;

const int MAX = 50000;

const int len = (1<<17);

// Globals.

int n;

int* order;

double* cosarr;

double* sinarr;

int* poly;

void fft(double* real, double* img, bool invert);

long long* multiply(int* a, int* b);

int* scale(long long* arr);

int* mypow(int* poly, int exp);

int main() {

    // Building order array for FFT.

    order = new int[2];

    order[0] = 0;

    order[1] = 1;

    int orderlen = 2;

    // Just iterate building next array from previous.

    while (orderlen != len) {

        int* tmp = new int[orderlen<<1];

        for (int i=0; i<orderlen; i++) {

            tmp[2*i] = order[i];

            tmp[2*i+1] = order[i] + orderlen;

        }

        delete [] order;

        order = tmp;

        orderlen <<= 1;

    }

    // Pre-calculate.

    cosarr = new double[len];

    for (int i=0; i<len; i++) cosarr[i] = cos(i*2*PI/len);

    sinarr = new double[len];

    for (int i=0; i<len; i++) sinarr[i] = sin(i*2*PI/len);

    int numCases;

    cin >> numCases;

    // Process each case.

    for (int loop=0; loop<numCases; loop++) {

        // Read in the polynomial.

        poly = new int[len];

        for (int i=0; i<len; i++) poly[i] = 0;

        int n;

        cin >> n;

        for (int i=0; i<n; i++) {

            double price;

            cin >> price;

            poly[(int)(100*price + .1)]++;

        }

        // Read in exponent and number of queries.

        int exp, numQ;

        cin >> exp >> numQ;

        // Exponentiate our polynomial.

        int* res = mypow(poly, exp);

        // Now handle the queries.

        for (int i=0; i<numQ; i++) {

            double price;

            cin >> price;

            cout << res[(int)(100*price + .1)] << endl;

        }

        cout << endl;

        // Clean up.

        delete [] res;

        if (exp > 1) delete [] poly;

    }

    // Clean up.

    delete [] order;

    delete [] cosarr;

    delete [] sinarr;

    return 0;

}

// Raises poly to the exp using our MOD and lopping off appropriate terms.

int* mypow(int* poly, int exp) {

    // Done.

    if (exp == 1) return poly;

    // Get the time savings here.

    if (exp%2 == 0) {

        int* halfway = mypow(poly, exp/2);

        long long* res = multiply(halfway, halfway);

        if (exp > 2) delete [] halfway;

        return scale(res);

    }

    // Slow way, never runs twice in a row.

    int* rest = mypow(poly, exp-1);

    long long* res = multiply(rest, poly);

    delete [] rest;

    return scale(res);

}

// Scales the polynomial arr - lops off terms past MAX and does MOD.

int* scale(long long* arr) {

    int* res = new int[len];

    for (int i=0; i<=MAX; i++)    res[i] = (int)(arr[i]%MOD);

    for (int i=MAX+1; i<len; i++) res[i] = 0;

    delete [] arr;

    return res;

}

void fft(double* real, double* img, bool invert) {

    // Re-order numbers to be in fft ordering for combination.

    double* tmp = new double[len];

    for (int i=0; i<len; i++) tmp[i] = real[order[i]];

    for (int i=0; i<len; i++) real[i] = tmp[i];

    delete [] tmp;

    tmp = new double[len];

    for (int i=0; i<len; i++) tmp[i] = img[order[i]];

    for (int i=0; i<len; i++) img[i] = tmp[i];

    delete [] tmp;

    // size is the size of each grouping (when we combine up) in fft.

    for (int size=2; size<=len; size<<=1) {

        // Set up angle and halfway pt.

        int half = (size>>1);

        int skip = len/size;

        int sign = !invert ? 1 : -1;

        // i is the starting index for this group, j indicates pairs.

        for (int i=0; i<len; i+=size) {

            double aReal = 1, aImg = 0;

            int index = 0;

            for (int j=0; j<half; j++) {

                double fReal = real[i+j], fImg = img[i+j];

                double sReal = real[i+j+half]*cosarr[index] - img[i+j+half]*sinarr[index];

                double sImg = img[i+j+half]*cosarr[index] + real[i+j+half]*sinarr[index];

                real[i+j] = fReal + sReal;

                img[i+j] = fImg + sImg;

                real[i+j+half] = fReal - sReal;

                img[i+j+half] = fImg - sImg;

                index = (index+sign*skip+len)%len;

            }

        }

    }

    // For inverse transformation, we divide by n (my len).

    if (invert) {

        for (int i=0; i<len; i++) {

            real[i] /= len;

            img[i] /= len;

        }

    }

}

long long* multiply(int* a, int* b) {

    // Copy a.

    double* reala = new double[len];

    for (int i=0; i<len; i++) reala[i] = a[i];

    double* imga = new double[len];

    for (int i=0; i<len; i++) imga[i] = 0.0;

    // Copy b.

    double* realb = new double[len];

    for (int i=0; i<len; i++) realb[i] = b[i];

    double* imgb = new double[len];

    for (int i=0; i<len; i++) imgb[i] = 0.0;

    // Transform into points.

    fft(reala, imga, false);

    fft(realb, imgb, false);

    // Store product pts here.

    double* realPts = new double[len];

    double* imgPts = new double[len];

    // Multiply points.

    for (int i=0; i<len; i++) {

        realPts[i] = reala[i]*realb[i] - imga[i]*imgb[i];

        imgPts[i] = reala[i]*imgb[i] + realb[i]*imga[i];

    }

    // Now, convert these points back to a polynomial.

    fft(realPts, imgPts, true);

    // Finally copy over into a result array without doubles.

    long long* res = new long long[len];

    for (int i=0; i<len; i++)

        res[i] = (long long)(realPts[i]+.5+1e-9);

    delete [] reala;

    delete [] imga;

    delete [] realb;

    delete [] imgb;

    delete [] realPts;

    delete [] imgPts;

    return res;

}

巴特西

2020.4.6--UCF Local Programming Contest 2017的正式赛

Problem E: Simple Darts

Problem F: Multimodal Transport

Problem G: Videogame Probability

Problem H: Maximum Non-Overlapping Increasing Subsequences

最新文章

热门文章