当前位置:网站首页>2016 CCPC Hangzhou Onsite
2016 CCPC Hangzhou Onsite
2022-07-07 09:47:00 【moyangxian】
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;
}
边栏推荐
- 高斯消元
- 【frida实战】“一行”代码教你获取WeGame平台中所有的lua脚本
- Impression notes finally support the default markdown preview mode
- What development models did you know during the interview? Just read this one
- H5 web player easyplayer How does JS realize live video real-time recording?
- **grafana安装**
- How will fashion brands enter the meta universe?
- golang select机制和超时问题怎么解决
- 2020CCPC威海 J - Steins;Game (sg函数、线性基)
- Can flycdc use SqlClient to specify mysqlbinlog ID to execute tasks
猜你喜欢
随机推荐
PLC信号处理系列之开关量信号防抖FB
C# Socke 服务器,客户端,UDP
flinkcdc 用sqlclient可以指定mysqlbinlog id执行任务吗
Windows starts redis service
PostgreSQL reports an error when creating a trigger,
Liunx command
Information Security Experiment 1: implementation of DES encryption algorithm
2020CCPC威海 J - Steins;Game (sg函数、线性基)
iNFTnews | 时尚品牌将以什么方式进入元宇宙?
其实特简单,教你轻松实现酷炫的数据可视化大屏
How to solve the problem of golang select mechanism and timeout
JS逆向教程第一发
nlohmann json
Colorbar of using vertexehelper to customize controls (II)
第一讲:包含min函数的栈
进程和线程的区别
2020浙江省赛
[Frida practice] "one line" code teaches you to obtain all Lua scripts in wegame platform
Vs2013 generate solutions super slow solutions
在EXCEL写VBA连接ORACLE并查询数据库中的内容