2016 CCPC Hangzhou Onsite

A ArcSoft’s Office Rearrangement（ greedy ）

The question ： take n Divide into numbers k The same number , One operation can merge two numbers or split a number into two numbers . Find the minimum number of operands

. ： Find out n Divide the sum of numbers by k Value s, Traversal array , take x add a[i]（ If x Not for 0, That is, there are remaining numbers in the last operation , To put a[i] Add to x Add one to the middle answer ）, use x Record the current number , When x>s When will x Split it into s, until x<s. A special sentence is required x==s The answer is not to add one .

#include<bits/stdc++.h>

using namespace std;
#define int long long
const int N=1e5+10;
int a[N];
int cas;
void solve(){
    
    int n,k;
    scanf("%lld%lld",&n,&k);
    int sum=0;
    for(int i=1;i<=n;i++){
    
        scanf("%lld",&a[i]);
        sum+=a[i];
    }
    if(sum%k){
    
        printf("Case #%lld: -1\n",++cas);
        return ;
    }
    int s=sum/k;
    int x=0,ans=0;
    for(int i=1;i<=n;i++){
    
        if(x>0) ans++;
        x+=a[i];
        while(x>s){
    
            x-=s;
            ans++;
        }
        if(x==s) x-=s;
    }
    printf("Case #%lld: %lld\n",++cas,ans);
}

signed main(){
    
    int T;
    scanf("%lld",&T);
    while(T--){
    
        solve();
    }
    return 0;
}

B Bomb(Tarjan+ Shrinkage point )

The question ： Yes n A bomb , Each bomb has a coordinate 、 Explosion range and detonation cost . Find the minimum cost of all bombs .

. ：Tarjan Find all strongly connected components , And then shrink a little bit , The degree of penetration is 0 The minimum cost of points is enough .

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N=1010;
const int INF=0x3f3f3f3f;
ll x[N],y[N],r[N],c[N];
ll ans;
int n,cas;
int cnt;
int low[N],num[N],dfn,du[N];
int scc[N],Stack[N],top;
vector<int>g[N];
ll w[N];
void dfs(int u){
    
    Stack[top++]=u;
    low[u]=num[u]=++dfn;
    for(int i=0;i<g[u].size();i++){
    
        int v=g[u][i];
        if(!num[v]){
    
            dfs(v);
            low[u]=min(low[v],low[u]);
        }
        else if(!scc[v])
            low[u]=min(low[u],num[v]);
    }
    if(low[u]==num[u]){
    
        cnt++;
        while(1){
    
            int v=Stack[--top];
            scc[v]=cnt;
            if(u==v) break;
        }
    }
}

void tarjan(){
    
    for(int i=1;i<=n;i++)
        if(!num[i])
            dfs(i);
}

void init(){
    
    for(int i=1;i<=n;i++) g[i].clear();
    cnt=top=dfn=0;
    memset(scc,0,sizeof(scc));
    memset(num,0,sizeof(num));
    memset(low,0,sizeof(low));
    memset(du,0,sizeof(du));
}

ll dis(ll x1,ll y1,ll x2,ll y2){
    
    return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
}

void solve(){
    
    scanf("%d",&n);
    init();
    for(int i=1;i<=n;i++)
        scanf("%lld%lld%lld%lld",&x[i],&y[i],&r[i],&c[i]);
    for(int i=1;i<=n;i++){
    
        for(int j=1;j<=n;j++){
    
            if(i==j) continue;
            ll d=dis(x[i],y[i],x[j],y[j]);
            if(d<=r[i]*r[i])
                g[i].push_back(j);
        }
    }
    /* for(int i=1;i<=n;i++){ for(int j=0;j<g[i].size();j++) cout<<g[i][j]<<" "; cout<<endl; } */
    tarjan();
   /* for(int i=1;i<=n;i++) cout<<scc[i]<<" "; cout<<endl; */
    memset(w,INF,sizeof(w));
    for(int i=1;i<=n;i++){
    
        int x=scc[i];
        w[x]=min(w[x],c[i]);
        for(int j=0;j<g[i].size();j++){
    
            int v=g[i][j];
            int y=scc[g[i][j]];
            if(x!=y) du[y]++;
        }
    }
    /* for(int i=1;i<=cnt;i++) cout<<du[i]<<" "; cout<<endl; */
    ll ans=0;
    //cout<<cnt<<endl;
    for(int i=1;i<=cnt;i++){
    
        if(du[i]==0)
            ans+=w[i];
    }
    printf("Case #%d: %lld\n",++cas,ans);
}

int main(){
    
    int T;
    scanf("%d",&T);
    while(T--){
    
        solve();
    }
    return 0;
}

C Car( greedy + Card accuracy )

The question ： Record the coordinates of a car passing at an integer time , Ask about the minimum time it takes to drive to the end .

. ： Because the speed is non decreasing , So greedily set the last leg of the journey as one second , The speed is the last part of the journey . Then there are two cases when traversing forward ：
1、 distance <= Speed , Then it takes one second , The speed becomes the current distance .

2、 distance > Speed , Then time equals distance / Speed +1, Speed equals distance / Time .

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
const int N=1e5+10;
const double eps=1e-8;
int cas;
int a[N];
void solve(){
    
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    a[0]=0;
    if(n==1){
    
        printf("Case #%d: 1\n",++cas);
        return ;
    }
    double v=1.0*(a[n]-a[n-1]);
    int ans=0;
    for(int i=n-1;i>=0;i--){
    
        double s=1.0*(a[i+1]-a[i]);
        if(v>=s){
    
            v=s;
            ans++;
        }
        else{
    
            int t=int((s-eps)/v)+1;
            v=s/t;
            ans+=t;
        }
    }
    printf("Case #%d: %d\n",++cas,ans);
}

signed main(){
    
    int T;
    scanf("%d",&T);
    while(T--){
    
        solve();
    }
    return 0;
}

D Difference( thinking + Two points )

The question ： Find the coincidence formula x=f(y,K)-y,y The number of .

. ： First guess y Only up to 10 position , It can be estimated that y yes 10 The number of digits is already the limit . So will y Divide into A*1e5+B This form . Then the formula required by the topic becomes x=f(A,k)+f(B,k)-(A*1e5-B), We calculated in advance 1e5 Inside f(B,k)-B All the numbers , Then enumeration A, You can find the number that meets the conditions by dichotomy among all the numbers .

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5;
int f[N+10];
int a[N+10];
int n,k,cas;

int qpow(int a,int b){
    
    int res=1;
    while(b){
    
        if(b&1) res=res*a;
        a=a*a;
        b>>=1;
    }
    return res;
}

int getnum(int x){
    
    int res=0;
    while(x){
    
        int s=x%10;
        res+=qpow(s,k);
        x/=10;
    }
    return res;
}

void init(){
    
    for(int i=0;i<=N;i++){
    
        f[i]=getnum(i);
        //cout<<i<<" "<<f[i]<<endl;
    }
    for(int i=0;i<=N;i++){
    
        a[i]=f[i]-i;
        //cout<<a[i]<<" "<<i<<endl;
    }
    sort(a,a+1+N);
}

void solve(){
    
    cin>>n>>k;
    init();
    int ans=0;
    for(int i=0;i<=N;i++){
    
        int s=n-f[i]+i*N;
        int p=lower_bound(a,a+1+N,s)-a;
        while(p<=N&&a[p]==s){
    
            //cout<<a[p]<<endl;
            ans++;
            p++;
        }
    }
    if(n==0) ans--;
    printf("Case #%lld: %lld\n",++cas,ans);
}

signed main(){
    
    int T;
    cin>>T;
    while(T--){
    
        solve();
    }
    return 0;
}

E Equation（dfs prune ）

The question ： give 1-9 The number of numbers , Ask how many kinds a+b=c The combination of .

. ： You can see that the answers are at most 36 Kind of , then dfs this 36 One possibility .

#include<bits/stdc++.h>

using namespace std;
const int N=10;
int a[N];
int ans,cas,cnt;
struct Node{
    
    int x,y,z;
}s[100];

void f(){
    
    for(int i=1;i<=9;i++){
    
        for(int j=1;j<=9;j++){
    
            //if(i+j<=9) ans++;
            if(i+j>9) continue;
            s[++cnt]={
    i,j,i+j};
        }
    }
    //cout<<cnt<<endl;
    //36
}

void dfs(int p,int res){
    
    if(p>cnt){
    
        ans=max(ans,res);
        return ;
    }
    if(cnt-p+res+1<=ans) return ;
    int x=s[p].x;int y=s[p].y;int z=s[p].z;
    if(a[x]&&a[y]&&a[z]){
    
        a[x]--;a[y]--;a[z]--;
        if(a[x]>=0&&a[y]>=0&&a[z]>=0)dfs(p+1,res+1);
        //cout<<x<<" "<<y<<" "<<z<<endl;
        a[x]++;a[y]++;a[z]++;
    }
    dfs(p+1,res);
}

void solve(){
    
    for(int i=1;i<=9;i++)
        scanf("%d",&a[i]);
    ans=0;
    dfs(1,0);
    printf("Case #%d: %d\n",++cas,ans);
}

int main(){
    
    f();
    int T;
    scanf("%d",&T);
    while(T--){
    
        solve();
    }
    return 0;
}

F Four Operations( greedy , simulation )

The question ： Give a string of n Numeric string for , Add ’+’、’-’、’*’、’/’. Maximize the answer .

. ： The final formula is A+B-CD/E, Obviously, we are greedy to let A+B As big as possible ,CD/E As small as possible ,C and D Take only one digit ,E Take one or two （ for example ：111991）. Directly simulate once to find the maximum value .

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
const int N=1e5+10;
ll a,b,c,d,e;
int cas;
string ss;
ll check(int p){
    
    ll res=-INF;
    d=ss[p]-'0';
    p--;
    c=ss[p]-'0';
    p--;


    ll s=0;
    for(int i=1;i<=p;i++)
        s=s*10+(ss[i]-'0');
    s+=ss[0]-'0';
    res=max(res,s);

    s=0;
    for(int i=0;i<p;i++)
        s=s*10+(ss[i]-'0');
    s+=ss[p]-'0';
    res=max(res,s);


    res=res-c*d/e;
    return res;
}

void solve(){
    
    cin>>ss;
    ll ans=-INF;
    int n=ss.size()-1;
    e=ss[n]-'0';
    ans=max(ans,check(n-1));
    e=(ss[n-1]-'0')*10+(ss[n]-'0');
    if(n>=5)ans=max(ans,check(n-2));
    printf("Case #%d: %lld\n",++cas,ans);
}

signed main(){
    
    int T;
    scanf("%d",&T);
    while(T--){
    
        solve();
    }
    return 0;
}

K Kingdom of Obsession（ Prime distance , Bipartite map matching ）

The question ：x take s+1 - s+n,y take 1 - n. Ask for all x%y==0.

. ： First of all, a prime number has only mod1 And it itself will ==0. Therefore, only two or more primes in the interval do not meet the conditions . stay 1e9 The distance between the two prime numbers in the does not exceed 600. So when min(n,s) Greater than 600 Time is not qualified . And then for the rest n The number can be matched by bipartite graph .

#include<bits/stdc++.h>

using namespace std;
const int N=610;
vector<int>g[N];
bool vis[N];
int match[N];
int n,s,cas;
void init(){
    
    memset(match,0,sizeof(match));
    for(int i=1;i<=n;i++)
        g[i].clear();
}

bool dfs(int u){
    
    for(int i=0;i<g[u].size();i++){
    
        int v=g[u][i];
        if(!vis[v]){
    
            vis[v]=true;
            if(!match[v]||dfs(match[v])){
    
                match[v]=u;
                return true;
            }
        }
    }
    return false;
}

void solve(){
    
    scanf("%d%d",&n,&s);
    if(n>s) swap(n,s);
    if(n>600){
    
        printf("Case #%d: No\n",++cas);
        return ;
    }
    init();
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if((s+j)%i==0)
                g[i].push_back(j);
    int ans=0;
    for(int i=1;i<=n;i++){
    
        memset(vis,false,sizeof(vis));
        if(dfs(i)) ans++;
    }
    if(ans==n)
        printf("Case #%d: Yes\n",++cas);
    else
        printf("Case #%d: No\n",++cas);
}

int main(){
    
    int T;
    scanf("%d",&T);
    while(T--){
    
        solve();
    }
    return 0;
}