Distribution of books
Time Limit: 8000/8000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Problem Description
zz6d likes reading very much, so he bought a lot of books. One day, zz6d brought n books to a classroom in school. The books of zz6d is so popular that K students in the classroom want to borrow his books to read. Every book of zz6d has a number i (1<=i<=n). Every student in the classroom wants to get a continuous number books. Every book has a pleasure value, which can be 0 or even negative (causing discomfort). Now zz6d needs to distribute these books to K students. The pleasure value of each student is defined as the sum of the pleasure values of all the books he obtains.Zz6d didn't want his classmates to be too happy, so he wanted to minimize the maximum pleasure of the K classmates. zz6d can hide some last numbered books and not distribute them,which means he can just split the first x books into k parts and ignore the rest books, every part is consecutive and no two parts intersect with each other.However,every classmate must get at least one book.Now he wonders how small can the maximum pleasure of the K classmates be.
1<=T<=10
1<=n<=2*105
1<=k<=n
-109<=ai<=109
InputInput contains multiple test cases.
The first line of the input is a single integer T which is the number of test cases. T test cases follow.
For each test case, the first line contains two integer n,k: the number of books and the number of his classmates. The second line contains n integers a1 ,a2,…, an−1,an. (aimeans the pleasure value of book i.)∑n<=2*105.
OutputFor each case, print the smallest maximum pleasure of the K classmates, and one line one case.
Sample Input
2 4 2 3 -2 4 -2 5 4 -1 -1 -1 -1 6
Sample Output
2 -1 HintIn the first example,classmate 1 get book 1,2, classmate 2 get book 3,4.the maximum pleasure is max((3-2),(4-2))=2; In the second example,he can ignore book 5 and spilt the first 4 books into 4 parts,give them to his classmates.
考虑二分答案对于每次二分答案（假设为x），如何判定x能否满足分为k份的要求呢？考虑动态规划令dp[i]表示前i个数最多能分成几段, 则
dp[i] = max(dp[j]) + 1;
(sum[i] - sum[j] <= x)如果直接dp，时间复杂度为n^2，显然会TLE!所以考虑离散化后权值线段树维护
#include<bits/stdc++.h>
using namespace std;
const long long llINF = 9223372036854775807;
const int INF = 2147483647;
const int maxn = 3e5 + 7;
const int mod = 1e9 + 7;
int T;
int n, k;
long long a[maxn], pre[maxn];
long long b[maxn];
long long ans = llINF;
int rk[maxn];
int num[maxn];
struct SegmentTree
{
int l, r;
int f;
} tree[maxn << 2];
void push_up(int root)
{
tree[root].f = max(tree[root << 1].f, tree[root << 1 | 1].f);
}
void build(int root, int l, int r)
{
tree[root].l = l;
tree[root].r = r;
if (l == r)
{
tree[root].f = -1000000000;
return;
}
else
{
int mid = (l + r) >> 1;
build(root << 1, l, mid);
build(root << 1 | 1, mid + 1, r);
push_up(root);
}
return;
}
int query(int root, int l, int r)
{
if (l <= tree[root].l && r >= tree[root].r)
return tree[root].f;
int res = -INF;
int mid = (tree[root].l + tree[root].r) >> 1;
if (l <= mid)
res = max(res, query(root << 1, l, r));
if (r > mid)
res = max(res, query(root << 1 | 1, l, r));
return res;
}
void change(int root, int x, int v)
{
if (tree[root].l == tree[root].r)
{
tree[root].f = v;
return;
}
int mid = (tree[root].l + tree[root].r) >> 1;
if (x <= mid)
change(root << 1, x, v);
else
change(root << 1 | 1, x, v);
push_up(root);
}
bool check(long long mid)
{
build(1, 0, n + 1);
/*
dp[i]表示前i个数最多能分成几段
for (int i = 1; i <= n; i++)
{
dp[i] =max(dp[j]) + 1;
(sum[i]-sum[j]<=mid)
sum[j]>=sum[i]-mid
}
*/
change(1, rk[0], 0);
for (int i = 1; i <= n; i++)
{
int p = lower_bound(b, b + 1 + n, pre[i] - mid) - b;
change(1, rk[i], query(1, p, n + 1) + 1);
}
if (query(1, 0, n) >= k)
{
ans = min(ans, mid);
return true;
}
return false;
}
void init()
{
ans = llINF;
memset(pre, 0, sizeof(pre));
memset(a, 0, sizeof(a));
memset(b, 0, sizeof(b));
memset(rk, 0, sizeof(rk));
memset(num, 0, sizeof(num));
memset(tree, 0, sizeof(tree));
}
int main()
{
scanf("%d", &T);
while (T--)
{
scanf("%d%d", &n, &k);
init();
for (int i = 1; i <= n; i++)
scanf("%lld", &a[i]);
for (int i = 1; i <= n; i++)
pre[i] = pre[i - 1] + a[i];
for (int i = 0; i <= n; i++)
b[i] = pre[i];
sort(b, b + n + 1);
for (int i = 0; i <= n; i++)
{
int tmp = lower_bound(b, b + 1 + n, pre[i]) - b;
rk[i] = tmp + num[tmp];
num[tmp]++;
}
long long L = -1e15, R = 1e15;
while (L <= R)
{
long long mid = (L + R) >> 1;
if (check(mid))
R = mid - 1;
else
L = mid + 1;
}
printf("%lld\n", ans);
}
return 0;
}
Fansblog
Time Limit: 2000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Problem Description
Farmer John keeps a website called ‘FansBlog’ .Everyday , there are many people visited this blog.One day, he find the visits has reached P , which is a prime number.He thinks it is a interesting fact.And he remembers that the visits had reached another prime number.He try to find out the largest prime number Q ( Q < P ) ,and get the answer of Q! Module P.But he is too busy to find out the answer. So he ask you for help. ( Q! is the product of all positive integers less than or equal to n: n! = n * (n-1) * (n-2) * (n-3) *… * 3 * 2 * 1 . For example, 4! = 4 * 3 * 2 * 1 = 24 )
InputFirst line contains an number T(1<=T<=10) indicating the number of testcases.
Then T line follows, each contains a positive prime number P (1e9≤p≤1e14)
OutputFor each testcase, output an integer representing the factorial of Q modulo P.
Sample Input
1 1000000007
Sample Output
328400734
乱搞就完事了，记得int_128。用威尔逊定理 + 质数的密度分布。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128 exl;
int judge(ll x){
for(ll i=2;i*i<=x;i++){
if(x%i==0){
return 0;
}
}
return 1;
}
ll qp(ll a,ll b,ll md){
ll res=1;
while(b){
if(b&1) res=(ll)((exl)1*res*a%(exl)md);
a=(ll)((exl)1*a*a%(exl)md);
b>>=1;
}
return res;
}
int main(){
int T;
while(scanf("%d",&T)!=EOF)
while(T--){
ll x;
scanf("%lld",&x);
ll res;
for(ll i=x-1;;i--){
if(judge(i)==1){
res=i;
break;
}
}
ll ans=1;
for(ll i=res+1;i<x;i++){
if(qp(i,x-2,x)<=res){
ans=(ll)((exl)ans*qp(i,x-2,x)%(exl)x);
}
}
printf("%lld\n",ans);
}
return 0;
}
Find the answer
Time Limit: 4000/4000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Problem Description
Given a sequence of n integers called W and an integer m. For each i (1 <= i <= n), you can choose some elements Wk (1 <= k < i), and change them to zero to make ∑ij=1Wj<=m. So what's the minimum number of chosen elements to meet the requirements above?.
InputThe first line contains an integer Q --- the number of test cases.
For each test case:
The first line contains two integers n and m --- n represents the number of elemens in sequence W and m is as described above.
The second line contains n integers, which means the sequence W.
1 <= Q <= 15
1 <= n <= 2*105
1 <= m <= 109
For each i, 1 <= Wi <= m
OutputFor each test case, you should output n integers in one line: i-th integer means the minimum number of chosen elements Wk (1 <= k < i), and change them to zero to make ∑ij=1Wj<=m.
Sample Input
2 7 15 1 2 3 4 5 6 7 5 100 80 40 40 40 60
Sample Output
0 0 0 0 0 2 3 0 1 1 2 3
对于第i个位置，怎样选择数字才会使满足条件情况下选择数字数目最少呢？很容易想到，需要选择前i-1个数中较大的数字，使其变为0基于这个思想，如果我们对于每个位置i都暴力去找最大的前几个数，显然会TLE!可以注意到，题目可以转化为前i-1个数中最多选出多少个数字和W[i]相加使得其和小于等于m（很容易想到，选择较小的数才会使选的数最多）。转化之后就很容易想到用线段树来维护了。我们对给定数组进行离散化，对于离散化之后的数组建立一颗线段树，线段树上的每个节点记录区间之和以及区间内数字个数。
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(ll i=(a);i<=(b);++i)
#define dep(i,a,b) for(ll i=(a);i>=(b);--i)
#define pb push_back
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define delf ll m=(l+r)>>1
typedef long long ll;
const ll maxn=(ll)2e5+100;
const ll mod=(ll)1e9+7;
ll a[maxn],b[maxn],id[maxn],ans[maxn];
ll sum[maxn<<2],num[maxn<<2];
ll n,m;
ll getid(ll x){return lower_bound(b+1,b+1+n,x)-b;}
void PushUp(int rt){
sum[rt]=sum[rt<<1]+sum[rt<<1|1];
num[rt]=num[rt<<1]+num[rt<<1|1];
}
void build(ll l,ll r,ll rt){
if (l==r){
sum[rt]=0;num[rt]=0;
return;
}
delf;
build(lson); build(rson); PushUp(rt);
}
ll query(ll rt,ll l,ll r,ll ql,ll qr,ll ty){
if(ql<=l&&r<=qr) {
if(ty==1) return sum[rt];
else return num[rt];
}
ll mid=(l+r)>>1,ans=0;
if(ql<=mid) ans+=query(rt<<1,l,mid,ql,qr,ty);
if(qr>mid) ans+=query(rt<<1|1,mid+1,r,ql,qr,ty);
return ans;
}
void update(ll rt,ll l,ll r,ll pos,ll val){
if(l==r){
num[rt]++; sum[rt]+=val;
return;
}
ll mid=(l+r)>>1;
if(pos<=mid) update(rt<<1,l,mid,pos,val);
else update(rt<<1|1,mid+1,r,pos,val);
PushUp(rt);
}
void solve(){
scanf("%lld%lld",&n,&m);
build(1,n,1);
rep(i,1,n) scanf("%lld",&a[i]),b[i]=a[i],ans[i]=0;
sort(b+1,b+1+n); rep(i,1,n) id[i]=getid(a[i]);
ll presum=0;
rep(i,1,n){
if(presum+a[i]>m){
ll l=1,r=n;
ll id1=-1,tt=0,t1=0,t2=0;
while(l<=r){
ll mid=(l+r)>>1;
ll qunum=query(1,1,n,mid,n,1);
if(presum-qunum+a[i]<=m){
l=mid+1; tt=qunum; id1=mid;
}
else r=mid-1;
}
t2=query(1,1,n,id1,n,2);
ll j=b[id1];
t1=ceil(1.0*((presum-tt+a[i])-m)/j);
ans[i]=t1+t2;
}
update(1,1,n,id[i],a[i]);
presum+=a[i];
}
rep(i,1,n) printf("%lld ",ans[i]);
puts("");
}
int main(){
int T;cin>>T;
while(T--) solve();
}
