奶昔队Round #1 热身
模拟,不过我做的时候不是模拟,是计算...(写了好久,还wa了几次),现在看了别人的代码写过一份。
#include <iostream>
#include <algorithm>
#define N 1005
using namespace std;
int n,x,y,a,h,l;
char ma[N<<1][N];
int main() {
cin>>n;
h=l=y=1000;
for(int i=1;i<=n;i++){
cin>>a;
while(a--) if(i&1) ma[++y][++x]='/';
else ma[--y][++x]='\\';
h=max(h,y);
l=min(l,y);
y+=i%2?1:-1;
}
for(int i=h;i>=l;i--){
for(int j=1;j<=x;j++)
if(ma[i][j])cout<<ma[i][j];
else cout<<" ";
cout<<endl;
}
}
sum=Σlowbit(x),x不超过limit。
贪心,把1到limit的所有lowbit求出来,按lowbit值从大到小排个序,每次取完一个就把sum减去一个数。
#include <iostream>
#include <algorithm>
#define lowbit(x) ((x)&-(x))
using namespace std;
int sum,limit,ans;
struct num{
int id,low,ok;
}a[100005];
int cmp(num a,num b){
return a.low>b.low;
}
int main() {
cin>>sum>>limit;
for(int i=1;i<=limit;i++){
a[i].id=i;
a[i].low=lowbit(i);
}
sort(a+1,a+limit+1,cmp);
for(int i=1;i<=limit&∑i++)
if(a[i].low<=sum){
a[i].ok=1;
ans++;
sum-=a[i].low;
}
if(sum==0){
cout<<ans<<endl;
for(int i=1;i<=limit;i++)if(a[i].ok)
cout<<a[i].id<<" ";
}else
cout<<"-1";
}
删除每个点,就需要它相邻的点(未删除的)权值和的代价,求全部点删完后的最小代价。
贪心,一定是删权值最大的点,那么删掉时,对于相邻的边,就是花费了较小的相邻点的权值,于是直接对每条边取小的点加起来。
#include <iostream>
#include <algorithm>
#define N 1005
using namespace std;
int n,m,ans,v[N],a,b;
int main() {
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>v[i];
for(int i=1;i<=m;i++){
cin>>a>>b;
ans+=min(v[a],v[b]);
}
cout<<ans;
}
奶昔队Round #1
问一张纸能分多少个尽量大的正方形
#include <iostream>
using namespace std;
long long a,b,ans;
int main(){
cin>>a>>b;
while(a%b){
ans+=a/b;
a%=b;
swap(a,b);
}
cout<<ans+a/b;
}
就是找5个相距固定的*,居然把字符串从1开始,智障了。
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int ok(char c){
return c=='*';
}
char s[10000];
int main() {
int n;
cin>>n;
cin>>s;
for(int l=1;l<=n;l++){
for(int j=0;j<n;j++){
int ans=ok(s[j]);
for(int a=1;a<=4;a++)
if(!ok(s[j+l*a]))ans=0;
if(ans){
puts("yes");
return 0;
}
}
}
puts("no");
return 0;
}
从叶子节点往根的方向,每两个兄弟的差值加到答案上,父节点的值加上较大的那个儿子的值。
#include <iostream>
using namespace std;
int n,a[1<<11],ans;
int main() {
cin>>n;
for(int i=2;i<(1<<(n+1));i++)
cin>>a[i];
for(int k=n;k;k--)
for(int i=(1<<k);i<(1<<(k+1));i+=2){
a[i>>1]+=max(a[i],a[i+1]);
ans+=max(a[i],a[i+1])-min(a[i],a[i+1]);
}
cout<<ans<<endl;
}
红糖果和蓝糖果均有开心值和重量,要总质量不超过c,开心值最大有多少。
#include <iostream>
#define ll long long
using namespace std;
ll c,hr,hb,wr,wb,ans;
int main() {
cin>>c>>hr>>hb>>wr>>wb;
if(wr>=c/wr||hr*wb<wr*hb&&wb<c/wb)
{
swap(wb,wr);
swap(hb,hr);
}
for(int i=0;i*i<=c&&i<=c/wb;i++)
ans=max(ans,(c-i*wb)/wr*hr+i*hb);
cout<<ans;
}
对于n(<=100万)位的字符串,问你每个前缀是否可以划分为ABAB..ABA的形式,其中A、B代表字符串(A或B可以为空),且B出现m次。
这种题目很不好想,对于我来说。
当前前缀P=SSSSS...SST=m个AB+1个A,AB一定是几个S组成,A为P的后缀
共有R个S,分到m组里,余下的则是A的前缀。
A里面有R%m个S
B里面有R/m-R%m个S
KMP算出循环节长度len=i-Next[i],则
循环次数R=i/len
如果i%len==0,代表全为S,算出来如果B为空也是可以的,
否则,B为空不可以。
#include <cstdio>
#define N 1000005
using namespace std;
char s[N];
int n,m,Next[N],ans[N];
int main() {
scanf("%d%d%s",&n,&m,s);
int k=-1,i=0;
Next[i]=k;
while(s[i])
if(k==-1||s[i]==s[k]){
Next[++i]=++k;
int len=i-Next[i],R=i/len;
if(i%len==0)
ans[i]=(R/m-R%m>=0);
else
ans[i]=(R/m-R%m>0);
}else k=Next[k];
for(int i=1;i<=n;i++)
printf("%d",ans[i]);
puts("");
}
对于100万个数围成的环,求最少能切几段,每段的和不超过b,有q次询问。
滑窗,from[i]表示from[i]到i是已经划分了的段,ans[i]表示from[i]到i的最少段数。
左端为j,右端为i。
一开始j到i为一段,如果超过b,j右移,这样就求出i为右端的最大的一段,然后i右移,
from[i]=from[j],ans[i]=ans[j]+1;相当于j结尾后面又划分了一段。
继续求直到i-from[i]≥n。
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<cstring>
typedef long long ll;
using namespace std;
const int MAXN = 1000000+10;
int a[MAXN*2];
int from[MAXN * 2], ans[MAXN * 2];
ll ss[MAXN*2];
int main(){
int n, q;
scanf("%d%d", &n, &q);
for(int i=1;i<=n;i++){
scanf("%d", &a[i]);
a[i+n] = a[i];
from[i]=i;
ans[i]=0;
}
for(int i=1;i<=2*n;i++) ss[i]=ss[i-1]+a[i];
for(int Q=1;Q<=q;Q++){
int lim;
scanf("%d", &lim);
memset(ans, 0, sizeof(ans));
//memset(from, 0, sizeof(from));
int j = 1;
for(int i=n+1;i<=2*n;i++){
while(ss[i]-ss[j]>lim) j++;
ans[i] = ans[j]+1;
from[i] = from[j];
if(i-from[i]>=n){
printf("%d\n", ans[i]);
break;
}
}
//printf("%d\n", ans[2*n]);
}
}