当前位置:网站首页>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;
}
边栏推荐
- 【原创】程序员团队管理的核心是什么?
- 印象笔记终于支持默认markdown预览模式
- CMD startup software passes in parameters with spaces
- 有没有大佬帮忙看看这个报错,有啥排查思路,oracle cdc 2.2.1 flink 1.14.4
- CDZSC_2022寒假个人训练赛21级(1)
- Lesson 1: finding the minimum of a matrix
- Nested (multi-level) childrn routes, query parameters, named routes, replace attribute, props configuration of routes, params parameters of routes
- Lecture 1: stack containing min function
- sql 里面使用中文字符判断有问题,哪位遇到过?比如value&lt;&gt;`无`
- 哈夫曼编码压缩文件
猜你喜欢
VSCode+mingw64
Using JWT to realize login function
JMeter JDBC batch references data as input parameters (the simplest method for the whole website)
Over 100000 words_ Ultra detailed SSM integration practice_ Manually implement permission management
Software modeling and analysis
How will fashion brands enter the meta universe?
H5网页播放器EasyPlayer.js如何实现直播视频实时录像?
Dynamics 365Online ApplicationUser创建方式变更
Mysql:select ... for update
使用BigDecimal的坑
随机推荐
12、 Sort
Create an int type array with a length of 6. The values of the array elements are required to be between 1-30 and are assigned randomly. At the same time, the values of the required elements are diffe
Oracle installation enhancements error
H5 web player easyplayer How does JS realize live video real-time recording?
如何使用clipboard.js库实现复制剪切功能
flinkcdc 用sqlclient可以指定mysqlbinlog id执行任务吗
NATAPP内网穿透
Dynamics 365online applicationuser creation method change
sql 里面使用中文字符判断有问题,哪位遇到过?比如value&lt;&gt;`无`
农牧业未来发展蓝图--垂直农业+人造肉
VSCode+mingw64
哈夫曼编码压缩文件
基于智慧城市与储住分离数字家居模式垃圾处理方法
根据热门面试题分析Android事件分发机制(一)
sqlplus乱码问题,求解答
【无标题】
Upload taro pictures to Base64
Kubernetes cluster capacity expansion to add node nodes
第十四次试验
How to use Mongo shake to realize bidirectional synchronization of mongodb in shake database?