备战省赛组队训练赛第一场（补题）
题目链接：http://icpc.upc.edu.cn/running.php?cid=1721
问题 C: 调酒壶里的酸奶
看到要求最少操作次数，或者最少步数之类的字眼，首先考虑bfs()；
这道题有AB两个容器，有6种操作，
1.A倒满
2.B倒满
3.A倒入B
4.B倒入A
5.A倒光
6.B倒光
bfs枚举每步操作即可得到答案。
#include
#include
#include
#include
#include
#includeusing namespace std;struct node{int a,b,s;
};int book[110][110];
int va,vb,vc;int bfs(){memset(book,0,sizeof(book));queueq;q.push({va,0,1});q.push({0,vb,1});// if(va==vc||vb==vc) return 1;book[va][0]=1;book[0][vb]=1;while(!q.empty()){node pos=q.front();q.pop();//操作1if(pos.a==vc||pos.b==vc) return pos.s;if(!book[va][pos.b]){q.push({va,pos.b,pos.s+1});book[va][pos.b]=1;}//操作2if(!book[pos.a][vb]){q.push({pos.a,vb,pos.s+1});book[pos.a][vb]=1;}//操作3 A->Bint e1=vb-pos.b;//B还能装e1if(e1 问题 D: 过分的谜题
很难受一道找规律题，没啥好说，直接上大佬的代码。
#include
#include
#include int main(){int n;while(scanf("%d",&n)!=EOF){if(n==1){ std::cout<<"0";continue;}int ans=1;int pos=2;while(pos!=1){if(pos<=n) pos*=2;else pos-=2*n-pos+1;ans++;}printf("%d\n",ans);}
} 问题 E: 不存在的泳池
问至少需要多少个抽水机，转化一下就是至少抽几次水，看到至少，考虑bfs，参照C题每个游泳池有两个操作，bfs枚举每一步操作。
#include
#include
#include
#include fps游戏
wa了好多好多好多发，放弃了
问题 G: 流连人间的苏苏
维护一个差分序列，比较简单。
#include
#include
#include
#includeusing namespace std;struct node
{int l,r;
}p[1005];int a[1005];
int ans[1005];int main()
{int n,d;cin>>n>>d;while(d--){int l,r;scanf("%d%d",&l,&r);a[r+1]--;a[l]++;int t=0;for(int i=1;i<=n+1;i++){ans[i]=ans[i-1]+a[i];if(ans[i]>0&&ans[i-1]==0){p[t].l=i;} else if(ans[i]==0){if(ans[i-1]>0) p[t++].r=i-1;}}printf("[%d,%d]",p[0].l,p[0].r);for(int i=1;i 问题 H: 路哥从不低头
向路哥低头。
问题 I: 闪闪发光
物品重量为2^{w_i}，要求每次举重的重量和必须是2的幂。
观察规律，2^n+2^n=2^(n+1)，所以每两个质量为w_i的物品可以看做一个w_i+1的物品，所以如果物品个数是偶数个，直接把每两个物品捆绑成一个，然后加到w_i+1的物品个数里面，如果是奇数个，就拿出一个来单独举重，然后把剩余的偶数个物品捆绑好后加到w_i+1的物品中。
#include
#include
#include
#includeusing namespace std;int sum[5000005];int main()
{int n;while(scanf("%d",&n)!=EOF){memset(sum,0,sizeof(sum));for(int i=0,a;i 问题 J: 小C的数学问题（来自队友的分治思路~）
前缀和维护+ST表+分治
答案区间要么是整个区间，要么是在区间最小值分成的左右两个区间中，分治计算左右两个区间，求出答案
#include
#include
#include
#include
#includeusing namespace std;const int inf=0x3f3f3f3f;struct node
{int l,r;long long s;
};struct node2
{int minn,id;friend bool operator <(node2 a,node2 b){return a.minnb.s&&a.s>c.s){return a;}if(b.s>a.s&&b.s>c.s){return b;}return c;
}int n,a[100005];
long long sum[100005];
node2 st[100005][50];node slove(int l,int r)
{if(l<1||r>n||l>r) return {0,0,-1};int k=log(r-l+1)/log(2);node2 a=min(st[l][k],st[r-(1<>n;for(int i=1;i<=n;i++)scanf("%d",&a[i]);for(int i=1;i<=n;i++)sum[i]=sum[i-1]+a[i];for(int i=1;i<=n;i++) st[i][0].minn=a[i],st[i][0].id=i;int t=log(n)/log(2)+1;for(int i=1;i 问题 K: 周期串plus（偷看的学长的代码）
数据太水了，正解应该是KMP
#include
#include
#include
#includeusing namespace std;char s[100005];int main()
{while(scanf("%s",s)!=EOF){int n=strlen(s);int ans=0;for(int i=1;i<=n;i++){if(n%i==0){int flag=1;for(int k=i;k
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！