2019 CCPC Wannafly Camp Day 1
自闭感受
第一次参加这种线下的算法Camp，不得不说和队友都是内心非常的小鸡动。上午开幕式wls讲了一堆话，差不多就是一起呲逼加鸡汤吧
（哈哈希望wls不要打死我）。下午就是day训练赛了，因为一个主力队友生病没来，带着一个新队友2排，直接跳过了图论和DP题，差点就死怼C构造和E暴零自闭了，最后发现J题原题一发A，最后C题放弃了构造去写了100*100的暴力过了（抹汗）。自己还是太菜了，还有好多成长空间，细节，第一解题反应，耐心等等。
不多说上题解（后期补题会更新其他能力范围内的题解）
思路：3维DP维护一个3维数组，表示(i,j)位置第K秒有多少糖果，通过k-1秒5个位置转移得到(i,j,k)
#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=10010;
int dp[20][20][maxn];
int mp[20][20];
int main(){
int n,m,c,xs,ys,xt,yt;
scanf("%d%d%d",&n,&m,&c);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)scanf("%d",&mp[i][j]);
scanf("%d%d%d%d",&xs,&ys,&xt,&yt);
memset(dp,-0x3f,sizeof(dp));
dp[xs][ys][0]=0;
for(int k=1;k<maxn;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
dp[i][j][k]=max({dp[i-1][j][k-1],dp[i][j+1][k-1],dp[i+1][j][k-1],dp[i][j-1][k-1],dp[i][j][k-1]})+(k%mp[i][j]==0?1:0);
}
int _max=-1;
for(int i=0;i<maxn;i++)if(dp[xt][yt][i]>=c){_max=i;break;}
printf("%d\n",_max);
}
思路：题目只有1和2的情况，如果ab互质则为1，如果不互质n为2，且一定存在答案（第一感觉是这样）。开始我对n=2的情况去构造，发现一直wa~~（菜哭了）~~，后来A了J题后重新换了100*100暴力枚举两组ai,bi。
#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e9+7;
const int mod=1e5+7;
int main(){
int t;
scanf("%d",&t);
while(t--){
ll a,b;
scanf("%lld%lld",&a,&b);
if(__gcd(a,b)==1){
printf("1\n%lld %lld\n",a,b);
}
else{
int flag=0;
for(ll i=2;i<=100;i++){
for(ll j=2;j<=100;j++){
if(__gcd(a-i,b-j)==1&&__gcd(i,j)==1){
printf("2\n%lld %lld\n",i,j);
printf("%lld %lld\n",a-i,b-j);
flag=1;
break;
}
}
if(flag)break;
}
}
}
return 0;
}
直接连边树形dp计算。需要注意的是图并非联通，可以使用并查集，判断这个集合是否已经处理过。
#include<bits/stdc++.h>
using namespace std;
const int maxn=110;
vector<int> e[maxn];
void add(int u,int v){e[u].push_back(v),e[v].push_back(u);}
int pre[maxn];
int fin(int x){return pre[x]==x?x:pre[x]=fin(pre[x]);}
void unio(int a,int b){pre[fin(a)]=fin(b);}
int f[maxn],d[maxn];
long long int dp[maxn][2];
bool vis[maxn];
void dfs(int u,int pre){
dp[u][1]=f[u];
for(int i=0;i<e[u].size();i++){
int v=e[u][i];
if(v==pre)continue;
dfs(v,u);
dp[u][0]+=max(dp[v][0],dp[v][1]);
dp[u][1]+=max(dp[v][0],dp[v][1]-d[min(u,v)]);
}
}
int main(){
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){scanf("%d",&f[i]);pre[i]=i;}
for(int i=1;i<=n;i++){scanf("%d",&d[i]);}
for(int i=2;i<=n;i++){
if((i&1) && (3*i+1<=n)){
add(i,3*i+1);
unio(i,3*i+1);
}
else if (i%2==0){
add(i,i/2);
unio(i,i/2);
}
}
long long ans=0;
for(int i=1;i<=n;i++){
int p=fin(i);
if(!vis[fin(i)]){
vis[fin(i)]=1;
dfs(fin(i),fin(i));
ans+=max(dp[fin(i)][0],dp[fin(i)][1]);
}
}
printf("%lld\n",ans);
return 0;
}
第一座山的高度确定了，R[1]。当前体力为k，山与山之间的边权为w。那么当后面山的高度大于R[1]+k的时候就需要将山的高度降低。上山消耗体力，下山增加体力，其实就相同高度低于R[1]的时候这个山不存在。因为如果碰到了一个在高的山，增加的体力就被抵消了，相同于没有。那就将边权加上多出来的那部分，（R[x]-（R[1]+k）)^2，然后跑最短路就行了。
#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
const long long inf=0x3f3f3f3f3f3f3f3f;
long long dis[maxn];
bool vis[maxn];
struct node{
int u;
long long dis;
bool operator < (const node &r)const{
return dis>r.dis;
}
};
struct edge{
int v;
long long w;
int next;
}e[maxn*10];
int head[maxn*10],hcnt=0;
int n,m,k;
void add(int u,int v,long long int w){
e[hcnt]=edge{v,w,head[u]};
head[u]=hcnt++;
}
void dij(int start){
priority_queue<node> que;
for(int i=1;i<=n;i++)
vis[i]=false,dis[i]=inf;
que.push({start,0});
dis[start]=0;
while(!que.empty()){
int u=que.top().u;
que.pop();
if(vis[u])continue;
vis[u]=1;
for(int i=head[u];i>=0;i=e[i].next){
int v=e[i].v;
if(dis[v]>dis[u]+e[i].w)
dis[v]=dis[u]+e[i].w,que.push({v,dis[v]});
}
}
}
long long int r[maxn];
int main(){
memset(head,-1,sizeof(head));
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;i++)scanf("%lld",&r[i]);
for(int i=1;i<=m;i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
add(u,v,w+max(0LL,r[v]-(r[1]+k))*max(0LL,r[v]-(r[1]+k)));
add(v,u,w+max(0LL,r[u]-(r[1]+k))*max(0LL,r[u]-(r[1]+k)));
}
dij(1);
printf("%lld\n",dis[n]);
return 0;
}
思路：看着题比较晚了，一看woc这不就是CF原题嘛，考虑枚举最终票数。枚举完票数就开始处理，把每个党超过这个票数且收钱最少的人收买过来，如果这些人都收买完了可是还没有达到预定的票数，就一直收买之前还没有收买过的学生直到人数达标,就这样巴拉巴拉A了
#include<stdio.h>
#include<bits\stdc++.h>
using namespace std;
typedef long long ll;
int n,m,ns,cnt[3005],Sum[3005];
struct peo{
int p,c,rk;
}a[3005];
struct val{
int rk,v;
}b[3005];
bool vis[3005];
ll min_ans=-1,ans;
bool cmpa (peo a,peo b){
if(a.p==b.p) return a.c<b.c;
return a.p<b.p;
}
bool cmpb (val a,val b){
return a.v<b.v;
}
int main(){
scanf("%d%d",&m,&n);
for (int i=1;i<=n;++i){
scanf("%d%d",&a[i].c,&a[i].p);
a[i].p++;
a[i].rk=i;
b[i].rk=i;
b[i].v=a[i].c;
}
sort(a+1,a+1+n,cmpa);
sort(b+1,b+1+n,cmpb);
for (int i=1;i<=n;++i)
Sum[ a[i].p ]++;
for (int s=1;s<=n;++s){
ns=0;
ans=0;
memset(vis,0,sizeof(vis));
memset(cnt,0,sizeof(cnt));
for (int j=1;j<=n;++j){
if(a[j].p==1) ns++,vis[ a[j].rk ]=true;
else{
if(Sum[ a[j].p ]-cnt[ a[j].p ]>=s){
vis[ a[j].rk ]=true;
cnt[ a[j].p ]++;
ans+=a[j].c;
ns++;
}
}
}
for (int i=1;i<=n;++i){
if(ns>=s) break;
if(vis[ b[i].rk ]) continue;
ns++;
ans+=b[i].v;
}
if(min_ans==-1) min_ans=ans;
min_ans=min(ans,min_ans);
}
cout<<min_ans;
return 0;
}
查看8道真题和解析
网易公司福利 162人发布