# Noip2016 ysy模拟1

tonyfang posted @ 2016年11月16日 18:29 in 随笔 with tags c++ OI , 1089 阅读

1. chess

$0\leq t, x0, y0 \leq 10^{12}, 0 \leq w,h \leq 50$

【题解】

# include <stdio.h>
# include <algorithm>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

const int M = 60;

int w, h;
ll t, x, y;

char s[M][M];

int main() {
freopen("chess.in", "r", stdin);
freopen("chess.out", "w", stdout);
scanf("%lld%lld%lld%d%d", &t, &x, &y, &w, &h);

for (int i=0; i<w; ++i)
for (int j=0; j<h; ++j) {
ll newx = x+i, newy = y+j;
//			printf("%lld %lld\n", newx, newy);
ll ss = newx + newy;
if(ss&1) s[i][j] = '.';
else {
ss=ss>>1;
if(ss+1<=t) {
//					printf("ss=%lld\n", ss);
if(ss&1) s[i][j] = 'B';
else s[i][j] = 'A';
if((ss&newy) != newy) s[i][j] = '.';
} else s[i][j] = '.';
}
}
for (int i=h-1; i>=0; --i, puts(""))
for (int j=0; j<w; ++j)
printf("%c", s[j][i]);

return 0;
}

// 5 4 1 3 4


2. shop

$n, m \leq 50, p \leq 16$。

【题解】

# include <stdio.h>
# include <algorithm>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

const int M = 60;

ll f[1<<18][M];

int n, m, p;
ll dis[M][M];

int l[M], r[M], t[M];

int main() {
freopen("shop.in", "r", stdin);
freopen("shop.out", "w", stdout);
scanf("%d%d%d", &n, &m, &p);
for (int i=0; i<n; ++i) {
for (int j=0; j<n; ++j)
dis[i][j] = 1ll<<40;
dis[i][i] = 0;
}
for (int i=0; i<(1<<p); ++i)
for (int j=0; j<n; ++j) f[i][j] = 1ll<<40;
for (int i=1; i<=m; ++i) {
int u, v;
ll c;
scanf("%d%d%lld", &u, &v, &c);
dis[u][v] = min(dis[u][v], c);
dis[v][u] = min(dis[v][u], c);
}
for (int k=0; k<n; ++k)
for (int i=0; i<n; ++i)
for (int j=0; j<n; ++j)
dis[i][j] = min(dis[i][j], dis[i][k]+dis[k][j]);
for (int i=0; i<p; ++i) scanf("%d%d%d", &l[i], &r[i], &t[i]);
f[0][n-1]=0;
int ans = 0;
for (int i=1; i<(1<<p); ++i) {
int mx=0;
for (int j=0; j<p; ++j) {
if(i&(1<<j)) {
++mx;
for (int k=0; k<n; ++k)
if(f[i^(1<<j)][k]+dis[j][k]<=r[j])
f[i][j] = min(f[i][j], max((ll)l[j], f[i^(1<<j)][k]+dis[j][k])+t[j]);
}
}
for (int j=0; j<n; ++j) {
if(f[i][j] < (1ll<<40))
ans = max(ans, mx);
}
}
printf("%d\n", ans);
return 0;
}


3. sequence

$m \leq n \leq 10^5, a_i \leq 10^9$。

【题解】

# include <stdio.h>
# include <algorithm>
# include <set>
# include <iostream>
# include <string.h>
# define abs(x) (x>0?x:-x)

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

const int M = 1000010;

int n, m;
ll a[M];

ll b[M];
int bn=0;
int S[M];
int fs[M], fsn=0;

struct node {
ll cur;
int id;
};

bool operator <(node a, node b) {
return a.cur>b.cur;
}

set<node> s;

int fa[M];
int fl[M], fr[M];

inline int getf(int x) {
return fa[x]==x ? x : fa[x] = getf(fa[x]);
}

inline void unions(int fx, int fy) {
fa[fx] = fy;
fl[fy] = min(fl[fy], fl[fx]);
fr[fy] = max(fr[fy], fr[fx]);
}

int main() {
freopen("sequence.in", "r", stdin);
freopen("sequence.out", "w", stdout);
while(~scanf("%d%d", &n, &m)) {
memset(b,0,sizeof(b));
memset(S,0,sizeof(S));
s.clear();
bn=fsn=0;
for (int i=1; i<=n; ++i) scanf("%lld", &a[i]);
int head=1, tail=n;
while(a[head]<0) ++head;
while(a[tail]<0) --tail;
int zf=1;
++bn;
for (int i=head; i<=tail; ++i) {
if(zf*a[i]>0 || (zf==1&&a[i]==0)) {
b[bn]+=a[i];
S[bn]++;
} else {
++bn;
b[bn]=a[i];
S[bn]=1;
zf=-zf;
}
}
int total1=0, total2=0;
ll tot=0;
for (int i=1; i<=bn; ++i) {
if(b[i]>=0) {
total1+=S[i];
total2++;
tot+=b[i];
}
}
if(m >= total2 && m <= total1) {
printf("%lld\n", tot);
} else if(m > total1) {
sort(a+1, a+n+1);
ll ans=0;int k=0;
for (int i=n;i>=1;--i) {
++k;
ans+=a[i];
if(k==m)break;
}
printf("%lld\n", ans);
} else if(m < total2) {
for (int i=1; i<=bn; ++i) {
b[i]=-abs(b[i]);
s.insert((node){b[i],i});
}
int res = total2 - m;
for (int i=1; i<=bn; ++i) fa[i] = i, fl[i] = fr[i] = i;
for (int i=1; i<=res; ++i) {
node x = *s.begin();
s.erase(x);
int fx = x.id, fll = fl[fx], frr = fr[fx];
tot=tot+x.cur;
int left=-1,right=-1;
if(fll > 1) left=getf(fll-1);
if(frr < bn) right=getf(frr+1);
b[fx]=-b[fx];
if(left!=-1) {
s.erase((node){b[left], left});
unions(left, fx);
b[fx]+=b[left];
}
if(right!=-1) {
s.erase((node){b[right], right});
unions(right, fx);
b[fx]+=b[right];
}
if(left!=-1 && right!=-1)
s.insert((node){b[fx],fx});
}
printf("%lld\n", tot);
}
}

return 0;
}


Gujarat STD-1 Model 说:
2022年9月11日 17:01

Gujarat State Department of School Education, Gandhinagar and the State level subject experts and other private school teaching staff of the Elementary Level Primary School have designed and suggested the GSEB 1st Class Model Paper 2023 with sample answers Set wide as SET-A, SET-B, SET-C and SET-D to know the new exam scheme or question pattern. Gujarat STD-1 Model Paper Students of the Gujarat state can download the NCERT & SCERT Syllabus GSEB STD-1 Question Paper 2023 Pdf with sample answers along with the class teacher’s suggested all lesson or chapter’s most important questions for Part-A, Part-B, Part-C and Part-D exams of Term-1 & Term-2 to the academic year of 2023.

Assam 7th Class Syl 说:
2023年7月14日 16:31

Assam 7th Class Syllabus 2024 will help Students to Prepare for pass Marks in All Exams the All Subjects, Assam Students to get a Clear idea of the Topics and Subtopics and According to it they can Decide on which topic to Focus more, Assam 7th Exam Conducted Every Year Month of March and April Months, This 7th Date Sheet 2024 Available at Official Website.as it helps Students to Plan their Preparations Assam 7th Class Syllabus 2024 Accordingly to Meet their Expectations, we Provide Students with All the Necessary Support and Allow them to Prove their Talent by performing best in their examination, The Students skill Profile Should move From being Predominantly Receptive to Productive.

(输入验证码)
or Ctrl+Enter