感想:过个年10多天没刷题,一开始连签到题都不是很顺利,而且一开始作死开了D题,结果全场有D,F两道题没人过,结果排在了3题尾,哭死。但这不是理由,最重要的原因是自己菜,而且寒假第一阶段所学的知识点还不会运用,因为寒假第一阶段是专题训练,每道题都有说考察什么知识点,而且这次排位赛E题考二分,我却想不到二分做,I题考优先队列,我却一直卡在那里,一直想模拟过程,B题考DP,我却一直想贪心,根本没有想到状态转移,C题却嫌麻烦,不想模拟,所以放弃。最终只做完三道签到题,被rank1差点7题的lyr大佬无情的锤爆
总而言之,题还是刷的比较少,不懂得系统的总结加以应用,好多只知道知识点,却不会应用到题目中去
【题目链接】:http://codeforces.com/group/NVaJtLaLjS/contest/238166
A.The Bucket List(签到题)
题意:给定N只奶牛,每只奶牛开始挤奶时间以及结束时间分别为s与t,以及每只奶牛在挤奶时间需要b只桶,问最多需要多少只桶?
思路:(由于题目数据1<= s,t <=1000,且保证在某个时刻只有一只奶牛开始挤奶或者结束挤奶,所以直接暴力就行)
复杂度O(1000)
#include
using namespace std;
typedef long long ll;
int a[1005],b[1005];
int main()
{
int n,s,e,c;
cin>>n;
for(int i=1;
i<=n;
i++)
{
cin>>s>>e>>c;
a[s]=b[e]=c;
}
int cnt=0,tmp=0,i;
for(i=1;
i<=1000;
i++)
{
if(a[i]){
if(a[i]<=tmp)
tmp-=a[i];
else{
cnt+=(a[i]-tmp);
tmp=0;
}
}
if(b[i])
{
tmp+=b[i];
}
}
cout<
B. Teamwork(dp)
题意: 给定n只奶牛,每只奶牛有一个技能点,把1-n只奶牛连续分成多组,每组奶牛不超过k只,每只奶牛只能存在一组,且该组的奶牛技能点都会升高到与组里某只奶牛最高技能点一样,如何分配,求得n只奶牛总的技能点最大
思路: dp,dp[i]表示前i只奶牛总的最大技能点,而且第i只奶牛会会受到前面k只奶牛影响,复杂度O(n*k)
#include
using namespace std;
typedef long long ll;
int a[10005],dp[10005];
int main()
{
int n,k;
ll sum=0;
cin>>n>>k;
for(int i=1;
i<=n;
i++)
cin>>a[i];
for(int i=1;
i<=n;
i++)
{
int maxx=-1;
for(int j=1;
j<=min(i,k);
j++)
{
maxx=max(maxx,a[i-j+1]);
dp[i]=max(dp[i],dp[i-j]+maxx*j);
}
}
cout<
C. Mooyo Mooyo(联通块dfs+简单模拟)
题意: 有点类似于消消乐,如果相邻同颜色的超过k块,就消去,消完后,若底下为空,由于重力会掉下去,问最后无法可消去后的方阵
思路: 先dfs一次求得各自相邻同颜色的方块数,若是满足>=k,则再dfs一次消去,接着模拟掉落过程,记住在地图mp[ ][ ]最底层为第n行,而不是第0行,模拟时不要写错,重复以上操作,直到符合条件结束循环
#include
using namespace std;
char mp[105][15],vis[105][15];
int n,k,cnt;
int dis[4][2]={1,0,0,1,-1,0,0,-1};
bool judge(int x,int y,char ch)
{
if(x<0||y<0||x>n||y>10||vis[x][y]||mp[x][y]!=ch)
return false;
else
return true;
}
void dfs1(int x,int y,char ch)
{
vis[x][y]=1;
for(int i=0;
i<4;
i++)
{
int nx=x+dis[i][0],ny=y+dis[i][1];
if(judge(nx,ny,ch))
{
cnt++;
dfs1(nx,ny,ch);
}
}
}
void dfs(int x,int y,char ch)
{
mp[x][y]='0';
for(int i=0;
i<4;
i++)
{
int nx=x+dis[i][0],ny=y+dis[i][1];
if(judge(nx,ny,ch))
dfs(nx,ny,ch);
}
}
int main()
{
cin>>n>>k;
for(int i=0;
i>mp[i];
while(1)
{
int flag=0;
for(int i=0;
i=k){
dfs(i,j,mp[i][j]);
flag=1;
}
}
}
for(int i=0;
i<10&&flag;
i++)
{
int t=n;
for(int j=n-1;
j>=0;
j--)
{
if(mp[j][i]!='0')
mp[--t][i]=mp[j][i];
}
for(int j=t-1;
j>=0;
j--)
mp[j][i]='0';
}if(!flag)
break;
}
for(int i=0;
i
D. Cowpatibility 不会…………
【GDUT 寒假排位赛一】E. Convention(二分)
题意: 给定N只牛与N只牛的到达时间,m只公交车,每只公交车有c个座位, 求牛最长的等待时间最小(保证cm>=n)
思路: 先sort,然后进行二分check,若等待时间为mid且能把n只牛运走,则r=mid,否则l=mid+1,注意最长等待时间并不是a[i]-a[i-1],而是a[i]-pre(pre为该俩公交车第一只牛到达的时间,而不是上一只牛到达的时间)
复杂度O(nlogn)
#include
using namespace std;
int a[100005];
int n,m,c;
int judge(int mid)
{
int pre=a[1],cnt=1,seat=1;
for(int i=2;
i<=n;
i++)
{
if(a[i]-pre>mid||seat==c)
{
seat=1;
cnt++;
pre=a[i];
}
else
{
seat++;
}
}
if(cnt<=m)
return 1;
return 0;
}
int main()
{
scanf("%d%d%d",&n,&m,&c);
for(int i=1;
i<=n;
i++)
scanf("%d",&a[i]);
sort(a+1,a+1+n);
int r=1000000000,l=0;
while(r-l>0)
{
int mid=(l+r)/2;
if(judge(mid))
r=mid;
else
l=mid+1;
}
printf("%d\n",r);
return 0;
}
F. Fine Dining 不会…………
G. Back and Forth(dfs)
题意: A,B两个仓库,一开始各有1000单位牛奶,与各有10只可以装牛奶的桶,桶的大小可能不一样。现在问第一天在仓库A随便选择一只桶装满牛奶,然后运到仓库B,第二天从仓库B中11只桶随便选择一只桶装满牛奶,运到仓库A,问经过这样的牛程两次之后仓库A的牛奶的量有多少种可能?
思路: 最多有10 * 11 * 11 * 11=13310中选择,然后dfs过程中进行适当的剪枝,如相同型号的桶只取一次,最后A仓库的总量范围为0-2000,因为一开始A与B各有1000单位,遍历0-2000确定共有几种可能,注意dfs过程中记得回溯
#include
using namespace std;
int a[105],b[105],num,c[2005];
void dfs(int t,int suma,int sumb)
{
if(t>4){
c[suma]=1;
return;
}
if(t%2){
for(int i=1;
i<=100;
i++)
{
if(a[i]){
b[i]++,a[i]--,t++;
dfs(t,suma-i,sumb+i);
a[i]++,b[i]--,t--;
}
}
}
else {
for(int i=1;
i<=100;
i++)
{
if(b[i]){
a[i]++,b[i]--,t++;
dfs(t,suma+i,sumb-i);
b[i]++,a[i]--,t--;
}
}
}}
int main()
{
memset(c,0,sizeof c);
for(int i=1;
i<=10;
i++)
{
cin>>num;
a[num]++;
}
for(int i=1;
i<=10;
i++)
{
cin>>num;
b[num]++;
}
dfs(1,1000,1000);
int cnt=0;
for(int i=0;
i<=2000;
i++)
if(c[i]==1)
cnt++;
cout<
H.Mixing Milk(签到题)
题意: 有3只桶容量分别为c1,c2,c3,且一开始桶里的牛奶分别为m1,m2,m3,现在从A桶倒到B桶,B桶倒到C桶,C桶倒到A桶,每次倾倒要么倒空,要么倒满,问倒100次之后,三只桶里各有多少牛奶
思路: 每次倾倒两只桶的容量符合公式为m1-min(m1,c2-m2),m2+min(m1,c2-m2)
#include
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int MAXN = 105 + 5;
int w[3],v[3];
void pour(int i, int j) {
int del = min(w[j] - v[j], v[i]);
v[i] -= del;
v[j] += del;
}
int main() {
for(int i = 0;
i < 3;
i++) {
cin >> w[i] >> v[i];
}
for(int i = 1;
i <= 100;
i++) {
if(i % 3 == 1) {
pour(0, 1);
}
else if(i % 3 == 2) {
pour(1, 2);
}
else if(i % 3 == 0) {
pour(2, 0);
}
}
for(int i = 0;
i < 3;
i++) cout <
I. Convention II(优先队列)
题意: 给定编号为1-N的N头牛,与每只牛到达的时间,以及吃草的时间,且牛编号小的权限大,每次只能有一只牛在吃草,在此期间若有其他牛到达,则需要等待,若是有多只牛同时等待,则编号小的牛优先吃草,求牛的最长的等待时间
思路: 先把牛的到达时间进行sort,然后把需要等待的牛加入优先队列,每当一头牛吃完,再从队列里取出id最小的牛,若期间有其他牛到达,则加入队列,直到队列清空,则看后续是否牛到达,若有到达,则不用进入队列,无需等待,可以直接吃草,在取出队列的过程中要维护使得等待时间的最大
#include
using namespace std;
struct node
{
int s,v,id;
bool operator <(node y)const{
return this->id>y.id;
}
}a[100005];
bool cmp(node x,node y)
{
if(x.s==y.s)
return x.vque;
int time=0,ans=0,k;
for(int i=1;
i<=n;
i++)
{
if(que.empty())
{
time=a[i].s+a[i].v;
for(k=i+1;
k<=n;
k++)
{
if(a[k].s<=time)
que.push(a[k]);
else break;
}
}
else {
node tmp=que.top();
que.pop();
ans=max(ans,time-tmp.s);
time+=tmp.v;
for(;
k<=n;
k++)
{
if(a[k].s<=time)
que.push(a[k]);
else break;
}
}
}
printf("%d\n",ans);
return 0;
}