10.25模拟赛
1 任务安排
manage.in/.out/.cpp1.1 问题描述你有 N 个工作，同一时刻只能做一个任务, 其中每个工作有其所需时间, 及完成的 Deadline(截止时间), 问要完成所有工作, 最迟要从什么时候开始。你最早可以从时间 0 开始工作。1.2 输入格式第一行一个整数 N，表示任务数量接下来 n 行，每行两个整数，T i ,S i ，分别表示该任务的持续时间和截止时间。1.3 输出格式输出一个整数，表示最晚的开始时间，如果不能完成，输出-1。1.4 样例输入43 58 145 201 161.5 样例输出3
1.6 数据规模及约定对于 40% 的数据，N <= 20对于 60% 的数据，N <= 1000对于 100% 的数据，1<= N <= 1000001<= T i <= 1000001<= S i <= 1000000
贪心
我们按每一个任务的结束时间排序，这样我们可以最后在处理这个任务，然后我们计算每个任务开始的时间，如果一个任务开始的时间<=她的下一个任务结束的时间，那么我们把这个任务结束的时间设为上一个任务结束的时间，因为任务可以提前完成，如果一个任务开始的时间>下一个任务结束的时间，那么我们把这个任务结束的时间即为这个任务结束的时间，因为我们不可以晚结束、、
T为我们剩下的时间，如果T<0的话，任务不能全部完成，否则输出T
#include#include #include #include #define N 100010using namespace std;int read(){ int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); return x*f;}struct Node{ int t,end;}node[N];int cmp(Node a,Node b){ return a.end>b.end;}int main(){ freopen("manage.in","r",stdin); freopen("manage.out","w",stdout); int n=read(); bool flag=false; for(int i=1;i<=n;i++) node[i].t=read(),node[i].end=read(); sort(node+1,node+1+n,cmp); int T=node[1].end; for(int i=1;i<=n;i++) { if(T<=node[i].end) T-=node[i].t; else T=node[i].end,T-=node[i].t; if(T<0) {flag=true;break;} } if(flag) printf("-1"); else printf("%d",T); return 0;}
2 小 a 的强迫症qiang.in/.out/.cpp2.1 问题描述小 a 是一名强迫症患者，现在他要给一群带颜色的珠子排成一列，现在有 N 种颜色，其中第 i 种颜色的柱子有 num(i) 个。要求排列中第 i 种颜色珠子的最后一个珠子，一定要排在第 i+1 种颜色的最后一个珠子之前。问有多少种排列珠子的方案。2.2 输入格式第一行一个整数 N，表示珠子颜色数量第二行 N 个整数，分别表示每种珠子的颜色数量2.3 输出格式
排列方案数，对 998244353 取余
2.4 样例输入
3
2 2 12.5 样例输出32.6 数据规模及约定共 3 种排列方案：1 2 1 2 31 1 2 2 32 1 1 2 3对于 40% 的数据，所有珠子数量和小于 15对于 80% 的数据，N <= 1000，所有珠子数量和小于 5000对于 100% 的数据，N <= 100000，所有珠子数量和小于 500000
组合数学+卢卡斯定理（组合数取模）
我们用一个sum数组记录一下珠子数量的前缀和，用s记录一下当前颜色的珠子的数量。对于一种珠子的最后一个排在他的后一个珠子的最后一个珠子之前，也就是说后面的珠子的最后一个一定是从他前的所有珠子的最后一个（现在它的位置是固定的了）那么还剩下s[i]-1个珠子，我们要把它放在sum[i]-1个珠子里的组合数为C(sum[i]-1,s[i]-1) -1减去的是最后一个珠子，然后我们在用一下乘法原理。我们还可以看到sum<=500000，也就是说我们的组合数要取模，那么我们就要用卢卡斯定理了
#include#include #include #include #define N 100010#define mod 998244353using namespace std;long long n,ans,s[N],sum[N],f[N]={ 1,1},a[N]={ 1,1},g[N]={ 1,1};long long read(){ long long x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); return x*f;}void work1(){ for(int i=2;i<=sum[n];i++) f[i]=f[i-1]*i; for(int i=2;i<=n;i++) ans=(ans%mod*(f[sum[i]-1]/f[s[i]-1]/(f[sum[i]-s[i]]))%mod)%mod; printf("%I64d",ans%mod);}int C(int n,int m){ return (f[n]%mod*g[m]%mod*g[n-m]%mod)%mod;}void work2(){ for(int i=2;i<=sum[n];i++) { f[i]=(f[i-1]%mod*i%mod)%mod; a[i]=(mod-mod/i)*a[mod%i]%mod; g[i]=g[i-1]*a[i]%mod; } for(int i=2;i<=n;i++) ans=(ans%mod*C(sum[i]-1,s[i]-1)%mod)%mod; printf("%I64d",ans%mod);}int main(){ freopen("qiang.in","r",stdin); freopen("qiang.out","w",stdout); n=read();ans=1; for(int i=1;i<=n;i++) s[i]=read(),sum[i]=sum[i-1]+s[i]; if(sum[n]<=15) work1(); else work2(); return 0;}
#include#include #include #include #define N 500010#define mod 998244353#define LL long long using namespace std;long long n,ans,s[N],sum[N],f[N];long long read(){ long long x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); return x*f;}int ins(int p){ f[0]=1; for(int i=1;i<=p;i++) f[i]=(f[i-1]%mod*i%mod)%mod;}LL MI(LL a,LL b,int p){ LL res=1; while(b) { if(b&1) res=(res%p*a%p)%p; b>>=1;a=(a%p*a%p)%p; } return res%mod;}LL C(LL n,LL m,int p){ if(m>n) return 0; return f[n]%p*MI(f[m]%p*f[n-m]%p,p-2,p)%p;}LL lus(LL n,LL m,int p){ if(m==0) return 1; return (C(n%p,m%p,p)%p*lus(n/p,m/p,p)%p)%p;}int main(){ freopen("qiang.in","r",stdin); freopen("qiang.out","w",stdout); n=read();ans=1; for(int i=1;i<=n;i++) s[i]=read(),sum[i]=sum[i-1]+s[i]; ins(sum[n]); for(int i=2;i<=n;i++) ans=(ans%mod*1LL*lus(sum[i]-1,s[i]-1,mod)%mod)%mod; printf("%I64d",ans%mod); return 0;}
3 函数求和sum.in/.out/.cpp3.1 问题描述你有一个含 N 个数字的数组 A，元素标号 1 到 N，同时他也有 N 个函数，也标号 1 到 N。第 i 个函数会返回数组中标号 L i 和 R i 之间的元素的和。现在有以下两种询问：1 x y 将数组的第 x 个元素修改为 y。2 m n 询问标号在 m 和 n 之间的函数的值的和。3.2 输入格式输入数据第一行包含一个整数 N，表示数组的长度和函数的数量。接下来的一行包含 N 个整数，表示数组中的元素 A i 。接下来的 N 行，每行包含两个整数 L i ,R i ，表示一个函数。接下来一行包含一个整数 Q，表示询问次数。下面 Q 行，每行一个询问，格式见题目描述。3.3 输出格式对于每个第 2 类询问，输出相应的答案。3.4 样例输入51 2 3 4 51 32 54 53 51 242 1 41 3 72 1 42 3 543.5 样例输出4153283.6 数据规模及约定对于前 20% 的数据: N ≤ 1000,Q ≤ 1000对于另外 30% 的数据: R i − L i ≤ 10, 所有的 x 各不相同对于 100% 的数据: 1 ≤ N ≤ 10 5 , 1 ≤ L i ≤ R i ≤ N, 1 ≤ x ≤ N,1 ≤ m ≤ n ≤ N, 1 ≤ A i ,y ≤ 10 9 , 1 ≤ Q ≤ 10
#include#include #include #include #define N 100010#define LL long longusing namespace std;int read(){ int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); return x*f;}struct Tree{ int l,r,v;}tree[N*4],node[N];int n,Q,a,b,x,y,p;long long ans;void build(int k,int l,int r){ tree[k].l=l,tree[k].r=r; if(tree[k].l==tree[k].r) { tree[k].v=read(); return ; } int mid=(l+r)>>1; build(k<<1,l,mid); build(k<<1|1,mid+1,r); tree[k].v=tree[k<<1].v+tree[k<<1|1].v;}void change(int k){ if(tree[k].l==tree[k].r) { tree[k].v=y; return ; } int mid=(tree[k].l+tree[k].r)>>1; if(x<=mid) change(k<<1); else change(k<<1|1); tree[k].v=tree[k<<1].v+tree[k<<1|1].v;}void ask(int k){ if(tree[k].l>=a&&tree[k].r<=b) { ans+=(LL)tree[k].v; return; } int mid=(tree[k].l+tree[k].r)>>1; if(a<=mid) ask(k<<1); if(b>mid) ask(k<<1|1);}int main(){ freopen("sum.in","r",stdin); freopen("sum.out","w",stdout); n=read();build(1,1,n); for(int i=1;i<=n;i++) node[i].l=read(),node[i].r=read(); Q=read(); while(Q--) { p=read(),x=read(),y=read(),ans=0; if(p==1) change(1); else { for(int i=x;i<=y;i++) a=node[i].l,b=node[i].r,ask(1); printf("%I64d\n",ans); } } return 0;}
#include#include #include #include using namespace std;typedef unsigned long long LL;#define lowbit(x) ((x)&-(x))int n;int a[100005];LL c[100005];int L[100005],R[100005];int Q;int t[405][100005];int belong[100005];// (i-1)/B+1LL sum[405];int B,NUM;void add(int x,LL d){ while(x<=n){ c[x]+=d; x+=lowbit(x); }}LL ask(int x){ LL ret=0; while(x){ ret+=c[x]; x-=lowbit(x); } return ret;}int main(){ freopen("sum.in","r",stdin); freopen("sum.out","w",stdout); scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); } for(int i=1;i<=n;i++){ scanf("%d%d",&L[i],&R[i]); } B=sqrt(n)+1;// printf("#%d\n",B); NUM=(n-1)/B+1; for(int i=1;i<=n;i++) belong[i]=(i-1)/B+1; for(int i=1;i<=n;i++) c[i]=a[i]; for(int i=1;i<=n;i++){ if(i+lowbit(i)<=n){ c[i+lowbit(i)]+=c[i]; } } for(int i=1;i<=n;i++){ t[belong[i]][L[i]]++; t[belong[i]][R[i]+1]--; } for(int i=1;i<=NUM;i++){ for(int j=1;j<=n;j++){ t[i][j]+=t[i][j-1]; sum[i]+=t[i][j]*1ULL*a[j]; } } scanf("%d",&Q); while(Q--){ int type,x,y; scanf("%d%d%d",&type,&x,&y); if(type==1){ for(int i=1;i<=NUM;i++){ sum[i]-=t[i][x]*1ULL*a[x]; sum[i]+=t[i][x]*1ULL*y; } add(x,-a[x]); a[x]=y; add(x,a[x]); }else{ int Ln,Rn; Ln=belong[x],Rn=belong[y]; LL ans=0; if(Ln==Rn){ for(int i=x;i<=y;i++){ ans+=ask(R[i])-ask(L[i]-1); } }else{ for(int i=Ln+1;i
距 NOIp2017 还剩 16 天
你可以做的事情还有很多，即使到最后一秒也不要放弃，因为不到结束的那一刻谁也不知道结果会怎样