比赛链接：http://codeforces.com/contest/846
A. Curriculum Vitae
题意：
解法：水题，直接模拟即可。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 105;
int n, a[maxn];
int main(){
scanf("%d", &n);
for(int i=1; i<=n; i++) scanf("%d", &a[i]);
int ans=0;
for(int i=0; i<=n; i++){
int cur = 0;
for(int j=1;j<=i;j++) cur+=a[j]==0;
for(int j=i+1;j<=n;j++) cur+=a[j]==1;
ans = max(ans, cur);
}
printf("%d\n", ans);
return 0;
}B. Math Show
题意：n个任务，每个任务包含k个子任务，每个子任务要花t[i]的时间，每完成一个子任务可以赚1块钱，如果完整的完成一个任务可以再追加赚1块钱，现在有M的时间，问在这个时间限制里面能赚的最多的钱。
解法：枚举完整完成的任务的个数，然后把时间排序，贪心算答案，取最大值。
#include <bits/stdc++.h>
using namespace std;
int t[50];
int main(){
int n, k, m, sum = 0;
scanf("%d%d%d",&n,&k,&m);
for(int i=1; i<=k; i++) scanf("%d", &t[i]), sum += t[i];
sort(t+1, t+k+1);
int ans = 0;
for(int i=0; i<=n; i++){
if(m<sum*i) continue;
int ff = m-sum*i;
int now = (k+1)*i;
for(int j=1; j<=k; j++){
int xishu = min(n-i, ff/t[j]);
now += xishu;
ff -= xishu*t[j];
}
ans = max(ans, now);
}
return 0*printf("%d\n", ans);
}C. Four Segments
题意：给了一个n个数的序列(n<=5000)，现在求一组(i,j,k)使得sum(0,i)-sum(i,j)+sum(j,k)-sum(k,n)最大，如果有多个最大值任意输出。
解法：直接O（n^3）枚举显然T,考虑优化。枚举一个j找到前面的最大值和后面的最大值就可以了，变成O(n^2)，开始是写的set找最大值，结果T了。就直接O(n)扫一遍。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 5010;
int n, a[maxn];
LL sum[maxn];
set <pair<LL,int>> s1, s2;
LL solve(int l, int r){
if(l==r) return 0;
else if(l==0) return sum[r-1];
else return sum[r-1]-sum[l-1];
}
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++) scanf("%d",&a[i]);
sum[0]=a[0];
for(int i=1;i<n;i++) sum[i]=sum[i-1]+a[i];
LL ans = -1e18;
int pos1, pos2, pos3;
for(int mid=0;mid<=n;mid++){
//s1.clear();
//s2.clear();
//for(int i=0;i<=mid;i++) s1.insert(make_pair(solve(0,i)-solve(i,mid), i));
//for(int i=mid;i<=n;i++) s2.insert(make_pair(solve(mid,i)-solve(i,n), i));
LL now1=-1e18, now2=-1e18;
int t1, t2;
for(int i=0;i<=mid;i++){
if(solve(0,i)-solve(i,mid)>now1){
now1=solve(0,i)-solve(i,mid);
t1=i;
}
}
for(int i=mid;i<=n;i++){
if(solve(mid,i)-solve(i,n)>now2){
now2=solve(mid,i)-solve(i,n);
t2=i;
}
}
if(ans < now1 + now2){
ans = now1 + now2;
pos1 = t1;
pos3 = t2;
pos2 = mid;
}
// ans = max(ans, (*s1.rbegin()).first+(*s2.rbegin()).first);
// if(ans==(*s1.rbegin()).first+(*s2.rbegin()).first){
// pos1 = (*s1.rbegin()).second;
// pos3 = (*s2.rbegin()).second;
// pos2 = mid;
// }
}
return 0*printf("%d %d %d\n", pos1, pos2, pos3);
}D. Monitor
题意：一份n*m的显示屏上某些像素点(xi,yi)在t[i]时间会坏掉，如果坏的像素点连成k*k大小，这个显示屏就不能用了，问显示屏损坏的最小的时间，如果不会损坏，输出-1
解法：直接2分时间，那么这个问题就变成了能否找到k*k的矩阵，直接二维前缀和O(n^2)即可。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 505;
int n,m,k,q,a[maxn][maxn],b[maxn][maxn],sum[maxn][maxn];
struct node{
int x,y,t;
}Q[maxn*maxn];
bool check(int x){
memset(b, 0, sizeof(b));
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
if(a[i][j]>=0) b[i][j] = (a[i][j]<=x);
}
}
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
b[i][j] += b[i-1][j];
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
b[i][j] += b[i][j-1];
for(int i=k; i<=n; i++){
for(int j=k; j<=m; j++){
if(b[i][j]-b[i-k][j]-b[i][j-k]+b[i-k][j-k]==k*k) return 1;
}
}
return 0;
}
int main(){
scanf("%d%d%d%d", &n,&m,&k,&q);
int l = 0, r = 0, ans;
memset(a, -1, sizeof(a));
for(int i=1; i<=q; i++){
scanf("%d%d%d", &Q[i].x,&Q[i].y,&Q[i].t);
a[Q[i].x][Q[i].y] = Q[i].t;
r = max(r, Q[i].t);
}
if(check(r+1) == false){
return 0*puts("-1");
}
while(l<=r){
int mid = (l+r)/2;
if(check(mid)) ans=mid,r=mid-1;
else l=mid+1;
}
printf("%d\n", ans);
return 0;
}E. Chemistry in Berland
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL inf = 110000000000000000;
const int maxn = 100010;
struct edge{
int to,next;
LL dis;
edge(){}
edge(int _to, int _next, LL _dis){
to = _to;
next = _next;
dis = _dis;
}
}E[maxn];
int n, edgecnt, head[maxn];
LL a[maxn], b[maxn];
void init(){
edgecnt = 0;
memset(head, -1, sizeof(head));
}
void add(int u, int v, LL w){
E[edgecnt].to = v, E[edgecnt].dis = w, E[edgecnt].next = head[u], head[u] = edgecnt++;
}
void dfs(int x, int fa, LL val){
for(int i=head[x]; ~i; i=E[i].next){
dfs(E[i].to, x, E[i].dis);
}
if(a[x]<b[x]) b[fa] += b[x]-a[x];
else if(a[x]>b[x]){
double tmp = (double)(b[x]-a[x])*val;
if(tmp<-inf){
printf("NO");
exit(0);
}
b[fa]-=(a[x]-b[x])*val;
if(b[fa]<-inf){
printf("NO");
exit(0);
}
}
}
int main(){
scanf("%d", &n);
init();
for(int i=1; i<=n; i++) scanf("%lld", &b[i]);
for(int i=1; i<=n; i++) scanf("%lld", &a[i]);
for(int i=2; i<=n; i++){
int x;
LL k;
scanf("%d%lld",&x,&k);
add(x, i, k);
}
for(int i=head[1];~i;i=E[i].next){
dfs(E[i].to, 1, E[i].dis);
}
if(b[1] < a[1]) return 0*puts("NO");
else return 0*puts("YES");
}
题意：一个数列，随机选l,r，f(l,r)为l,r区间内数的种数，问f(l,r）的期望
解法：sum(每个数算出他的贡献)/(n*n)，我们这只考虑l<=r ,对于当前这数字他能贡献后面的所有区间，但是对于前面的话，他只共贡献到前一个相同的数后面 ，比如 1 2 3 4 2 5 6 对于第一个2 他贡献于 (1,2) (1,3)(1,4)(1,5)(1,6)(1,7)(2,2) (2,3)(2,4)(2,5)(2,6)(2,7) 对于第2个2 贡献于 (3,5)(3,6)(3,7) (4,5)(4,6)(4,7) (5,5)(5,6)(5,7)
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+10;
typedef long long LL;
int last[maxn];
int main(){
int n,x;
LL ans = 0;
scanf("%d", &n);
for(int i=1; i<=n; i++){
scanf("%d", &x);
ans += 1LL*(i-last[x])*(n-i+1);
last[x]=i;
}
ans=ans*2-n;
printf("%.5f\n", ans*1.0/(1LL*n*n*1.0));
return 0;
}
京公网安备 11010502036488号