当前位置:网站首页>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;
}
边栏推荐
- VSCode+mingw64+cmake
- Flex flexible layout
- 2020浙江省赛
- The difference between viewpager2 and viewpager and the implementation of viewpager2 in the rotation chart
- 【无标题】
- Schema-validation: wrong column type encountered in column XXX in table XXX
- Loxodonframework quick start
- iNFTnews | 时尚品牌将以什么方式进入元宇宙?
- How to use clipboard JS library implements copy and cut function
- Lesson 1: hardness of eggs
猜你喜欢
Software modeling and analysis
JS reverse tutorial second issue - Ape anthropology first question
Oracle installation enhancements error
Information Security Experiment 4: implementation of IP packet monitoring program
[4G/5G/6G专题基础-147]: 6G总体愿景与潜在关键技术白皮书解读-2-6G发展的宏观驱动力
Strategic cooperation subquery becomes the secret weapon of Octopus web browser
Unity shader (learn more about vertex fragment shaders)
CSDN salary increase technology - learn about the use of several common logic controllers of JMeter
【无标题】
PLC信号处理系列之开关量信号防抖FB
随机推荐
消费互联网的产业链其实是很短的,它仅仅承接平台上下游的对接和撮合的角色
PostgreSQL创建触发器的时候报错,
CSDN salary increase technology - learn about the use of several common logic controllers of JMeter
IIS faked death this morning, various troubleshooting, has been solved
小程序弹出半角遮罩层
esp8266使用TF卡并读写数据(基于arduino)
Kubernetes cluster capacity expansion to add node nodes
CDZSC_2022寒假个人训练赛21级(2)
Information Security Experiment 2: using x-scanner scanning tool
C# Socke 服务器,客户端,UDP
大佬们,有没有遇到过flink cdc读MySQLbinlog丢数据的情况,每次任务重启就有概率丢数
Diffusion模型详解
CodeForces - 1324D Pair of Topics(二分或双指针)
flinkcdc 用sqlclient可以指定mysqlbinlog id执行任务吗
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
Elaborate on MySQL mvcc multi version control
Unity shader (data type in cghlsl)
Information Security Experiment 4: implementation of IP packet monitoring program
其实特简单,教你轻松实现酷炫的数据可视化大屏
How to become a senior digital IC Design Engineer (1-6) Verilog coding Grammar: Classic Digital IC Design