1 任务安排
manage.in/.out/.cpp
1.1 问题描述
你有 N 个工作，同一时刻只能做一个任务, 其中每个工作有其所需时
间, 及完成的 Deadline(截止时间), 问要完成所有工作, 最迟要从什么时候开
始。
你最早可以从时间 0 开始工作。
1.2 输入格式
第一行一个整数 N，表示任务数量
接下来 n 行，每行两个整数，T i ,S i ，分别表示该任务的持续时间和截
止时间。
1.3 输出格式
输出一个整数，表示最晚的开始时间，如果不能完成，输出-1。
1.4 样例输入
4
3 5
8 14
5 20
1 16
1.5 样例输出
2
1.6 数据规模及约定
对于 40% 的数据，N <= 20
对于 60% 的数据，N <= 1000
对于 100% 的数据，1<= N <= 100000
1<= T i <= 100000
1<= S i <= 1000000
#include<iostream> #include<cstdio> #include<algorithm> #define maxn 100001 using namespace std; int n,pos; struct node{ int t,s; bool operator < (const node b)const{ return s<b.s; } }a[maxn]; int main(){ freopen("manage.in","r",stdin);freopen("manage.out","w",stdout); scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d%d",&a[i].t,&a[i].s); sort(a+1,a+n+1); pos=a[n].s; for(int i=n;i>=1;i--){ pos=min(pos,a[i].s); pos-=a[i].t; } if(pos<0)puts("-1"); else printf("%d",pos); }
2 小 a 的强迫症
qiang.in/.out/.cpp
2.1 问题描述
小 a 是一名强迫症患者，现在他要给一群带颜色的珠子排成一列，现在
有 N 种颜色，其中第 i 种颜色的柱子有 num(i) 个。要求排列中第 i 种颜色
珠子的最后一个珠子，一定要排在第 i+1 种颜色的最后一个珠子之前。问
有多少种排列珠子的方案。
2.2 输入格式
第一行一个整数 N，表示珠子颜色数量
第二行 N 个整数，分别表示每种珠子的颜色数量
2.3 输出格式
排列方案数，对 998244353 取余
2.4 样例输入
3
2 2 1
2.5 样例输出
3
2.6 数据规模及约定
共 3 种排列方案：
1 2 1 2 3
1 1 2 2 3
2 1 1 2 3
对于 40% 的数据，所有珠子数量和小于 15
对于 80% 的数据，N <= 1000，所有珠子数量和小于 5000
对于 100% 的数据，N <= 100000，所有珠子数量和小于 500000
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define MAXN 100100 #define MAXM 501000 #define mod 998244353 using namespace std; int n,col[MAXN]; long long ans,sum,tot; long long C[5010][5010]; int main(){ //freopen("qiang.in","r",stdin);freopen("qiang.out","w",stdout); scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&col[i]); tot+=col[i]; } C[0][0]=1; for(int i=1;i<=tot;i++) for(int j=0;j<=i;j++) C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod; ans=1;sum=0; for(int i=1;i<=n;i++){ ans=ans*C[sum+col[i]-1][col[i]-1]%mod; sum+=col[i]; } cout<<ans<<endl; }
#include<iostream> #include<cstdio> #include<cstring> #define N 1000007 #define mod 998244353 #define ll long long using namespace std; ll n,m,ans,cnt; ll f[N]={1,1},fac[N]={1,1},inv[N]={1,1}; ll num[N],sum[N]; inline ll read() { ll x=0,f=1;char c=getchar(); while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } void init() { for(int i=2;i<=N;i++) { fac[i]=(fac[i-1]%mod*i%mod)%mod; f[i]=(mod-mod/i)*f[mod%i]%mod; inv[i]=inv[i-1]*f[i]%mod; } } ll C(int a,int b) { if(a<b) return 1; return fac[a]%mod*inv[b]%mod*inv[a-b]%mod; } int main() { freopen("qiang.in","r",stdin); freopen("qiang.out","w",stdout); n=read(); for(int i=1;i<=n;i++) num[i]=read(),sum[i]=sum[i-1]+num[i]; init();ans=1; for(int i=2;i<=n;i++) { ans=(ans%mod*C(sum[i]-1,num[i]-1)%mod)%mod; ans%=mod; } cout<<ans%mod<<endl; fclose(stdin);fclose(stdout); return 0; }
3 函数求和
sum.in/.out/.cpp
3.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 样例输入
5
1 2 3 4 5
1 3
2 5
4 5
3 5
1 2
4
2 1 4
1 3 7
2 1 4
2 3 5
3.5 样例输出
41
53
28
3.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<iostream> #include<cstdio> #include<vector> #include<ctime> #define maxn 100010 #ifdef WIN32 #define PLL "%I64d" #else #define PLL "%lld" #endif using namespace std; vector<int>to[100010]; long long tr1[maxn<<4],a[maxn]; struct node{ int l,r; }f[maxn]; int n,q; void add1(int pos,int del){ while(pos<=n){ tr1[pos]+=del; pos+=(pos&-pos); } } long long query1(int pos){ long long res=0; while(pos){ res+=tr1[pos]; pos-=(pos&-pos); } return res; } int main(){ //freopen("Cola.in","r",stdin); freopen("sum.in","r",stdin);freopen("sum.out","w",stdout); scanf("%d",&n); int op,x,y; for(int i=1;i<=n;i++){ scanf("%d",&a[i]); add1(i,a[i]); } int l,r; for(int i=1;i<=n;i++)scanf("%d%d",&f[i].l,&f[i].r); scanf("%d",&q); while(q--){ scanf("%d%d%d",&op,&x,&y); if(op==1){ add1(x,y-a[x]); a[x]=y; } else { long long ans=0; for(int i=x;i<=y;i++){ ans+=query1(f[i].r)-query1(f[i].l-1); } printf(PLL"\n",ans); } } //cout<<endl<<clock(); }