2021年初ICPC 天梯赛选拔赛第五场

A. 序列

思路：前缀和，对于每个每个区间(Li,Ri,Ci),那么sum[Li1]+Ci>=sum[Ri]，然后把每个这样的区间看作一条边，建图，用差分约束的思想跑SPFA，答案即为最小的数

#include 
#define ll long long
using namespace std;int n,p[100000],cnt=1;
struct Edge{int a,b,d,nt;Edge(int aa=0,int bb=0,int dd=0,int nn=0){a=aa;b=bb;d=dd;nt=nn;}
}e[100000];void add(int x,int y,int w){e[cnt]=Edge(x,y,w,p[x]);p[x]=cnt++;
}
int a[2010],c[1010],dis[100000];
bool vis[100000];
queue<int>q;int spfa() {memset(dis,0,sizeof(dis));q.push(a[2]);dis[a[2]]=0;while(!q.empty()){int k=q.front();q.pop();vis[k]=false;for(int i=p[k];i;i=e[i].nt){int kk=e[i].b;if(dis[kk]<dis[k]+e[i].d){dis[kk]=dis[k]+e[i].d;if(!vis[kk]){vis[kk]=true;q.push(kk);}}}}return dis[a[n<<1|1]];
}
int main()
{scanf("%d",&n);for(int i=1; i<=n; i++) {scanf("%d %d %d",&a[i<<1],&a[i<<1|1],&c[i]);a[i<<1|1]++;add(a[i<<1],a[i<<1|1],c[i]);}sort(a+2,a+2+(n<<1));for(int i=2; i<(n<<1|1); i++){add(a[i],a[i+1],0);add(a[i+1],a[i],a[i]-a[i+1]);add(a[2],a[i+1],0);}printf("%d",spfa());
} 

B. 矩形

思路：暴力，枚举矩形的上下界，O(m)统计确定上下界的矩形个数，时间复杂度：O(mn^2)

#include 
#define ll long long
using namespace std;
int n,m,ans;
bool mp[888][888],fa[888];
char s[888];int main()
{scanf("%d%d",&n,&m);for(int i=1; i<=n; i++) {scanf("%s",s);for(int j=1; j<=m; j++)mp[i][j] = (s[j-1]=='.'?true:false);}for(int up=1; up<=n; up++) {memset(fa,0,sizeof(fa));for(int down=up; down<=n; down++) {for(int i=1; i<=m; i++)if(!mp[down][i])  fa[i]=true;for(int l=1; l<=m; l++){int r=l;while(!fa[r]&&r<=m)  r++;ans += ((r-l+1)*(r-l))>>1;l=r;}}}printf("%d",ans);	return 0;
}

C. 锁

思路：找规律，多写几个，写到20左右一般就能看出规律了

#include 
#define ll long long
using namespace std;
ll K,n,l,r;ll qwq(int p,ll k)
{if(p<0)  return 0;ll h=(1l<<p);if(k<=h)  return qwq(p-1,k);else if(k==h+1)  return qwq(p-1,h)+h;else  return qwq(p-1,k-h-1)+h;
}ll Max(int p,ll k)
{if(p<0)  return 0;ll h=(1ll<<p);if(k<=h)  return Max(p-1,k);ll now=qwq(p,h+1);if(k==h+1)  return now;else return max(now,Max(p,k-h-1)+h);
}int main()
{scanf("%d %lld",&n,&K);ll ans=Max(n-1,K);for(int i=n-1; i>=0; i--)cout<<(((1ll<<i)&ans)?"1":"0");
}

E. 学生分组

思路：贪心，考虑低于下限和高于上限的组

#include 
#define ll long long
using namespace std;int main()
{int n,i,s=0,r,l,x=0,y=0,s1;int a[51]={};scanf("%d",&n);for(i=1; i<=n; i++)scanf("%d",&a[i]);scanf("%d %d",&l,&r);for(i=1; i<=n; i++){s += a[i];if(a[i]>r)	x=x+a[i]-r;if(a[i]<l)	y=y+l-a[i];}if(s<n*l||s>n*r){printf("-1");return 0;}if(x>y)	 printf("%d",x);else  printf("%d",y);return 0;
}

F. 阶乘问题

#include 
#define ll long long
using namespace std;
int s[1010];int main()
{int t,num,n,a,p[4]={6,2,4,8};cin>>t;while(~scanf("%d",&n)) {num=n;a=0;while(num) {if(num%5==2)  a+=1;else if(num%5==4)  a+=2;a += num/5;num /= 5;}if(n>1)  printf("%d\n",p[a%4]);else printf("1\n");}
}

H. 田忌赛马

思路：这题做法比较多…贪心/DP/转化成最佳二分图匹配以后用费用流（这个还是算了，没必要QAQ），采用贪心。下面引用一个很好的说明：

#include 
#define ll long long
using namespace std;
const int mod = 65964;
int a[10010],b[10010];int main()
{int n;scanf("%d",&n);for(int i=1; i<=n; i++)  scanf("%d",&a[i]);for(int i=1; i<=n; i++)  scanf("%d",&b[i]);sort(a+1,a+n+1);sort(b+1,b+n+1);int la=1,lb=1,ra=n,rb=n,ans=0;for(int i=1; i<=n; i++){if(a[la]>b[lb]) {la++,lb++,ans+=200;}else if(a[la]<b[lb]) {la++,rb--,ans-=200;}else {if(a[ra]>b[rb]) {ra--,rb--,ans+=200;}else if(a[ra]<b[rb]) {la++,rb--,ans-=200;}else {if(a[la]>b[rb])  ans+=200;else if(a[la]<b[rb])  ans-=200;la++,rb--;}}}cout<<ans<<endl;return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！