Everything Is Generated In Equal Probability
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Problem Description
One day, Y_UME got an integer N and an interesting program which is shown below:
Y_UME wants to play with this program. Firstly, he randomly generates an integer n∈[1,N] in equal probability. And then he randomly generates a permutation of length n in equal probability. Afterwards, he runs the interesting program(function calculate()) with this permutation as a parameter and then gets a returning value. Please output the expectation of this value modulo 998244353.
A permutation of length n is an array of length n consisting of integers only ∈[1,n] which are pairwise different.
An inversion pair in a permutation p is a pair of indices (i,j) such that i>j and pi<pj. For example, a permutation [4,1,3,2] contains 4 inversions: (2,1),(3,1),(4,1),(4,3).
In mathematics, a subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements. Note that empty subsequence is also a subsequence of original sequence.
Refer to https://en.wikipedia.org/wiki/Subsequence for better understanding.
InputThere are multiple test cases.
Each case starts with a line containing one integer N(1≤N≤3000).
It is guaranteed that the sum of Ns in all test cases is no larger than 5×104.
OutputFor each test case, output one line containing an integer denoting the answer.
Sample Input
1 2 3
Sample Output
0 332748118 554580197
乱搞题，打个表找规律就出来了
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
const int mod=998244353;
int n;
ll a,b;
ll qpow(ll base,ll n){
ll res=1;
while(n){
if(n&1) res=res*base%mod;
base=base*base%mod;
n>>=1;
}
return res%mod;
}
ll inv(ll b){return qpow(b,mod-2)%mod;}
void solve(){
if(n==1){printf("0\n");return;}
a=(n*n-1)%mod;
printf("%lld\n",a*b%mod);
}
int main(){
b=inv(9)%mod;
while(~scanf("%d",&n)) solve();
}
Just Skip The Problem
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)
Problem Description
Y_UME has just found a number x in his right pocket. The number is a non-negative integer ranging from 0 to 2n−1 inclusively. You want to know the exact value of this number. Y_UME has super power, and he can answer several questions at the same time. You can ask him as many questions as you want. But you must ask all questions simultaneously. In the i-th question, you give him an integer yi ranging from 0 to 2n−1 inclusively, and he will answer you if x&yi equals to yi or not. Note that each question you ask has a index number. Namely, the questions are ordered in certain aspect. Note that Y_UME answer all questions at the same time, which implies that you could not make any decision on the remaining questions you could ask according to some results of some of the questions.
You want to get the exact value of x and then minimize the number of questions you will ask. How many different methods may you use with only minimum number of questions to get the exact value of x? You should output the number of methods modulo 106+3.
Two methods differ if and only if they have different number of questions or there exsits some i satisfying that the i-th question of the first method is not equal to the i-th of the second one.
InputThere are multiple test cases.
Each case starts with a line containing one positive integer n(n≤109).
OutputFor each test case, output one line containing an integer denoting the answer.
Sample Input
2
Sample Output
2
签到题，最优的方案必然是每次询问一个位的具体值，一共有 个二进制位，方案数显然为n！
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll md=1e6+3;
ll a[md+10];
int main(){
a[0]=1;
for(int i=1;i<=md;i++){
a[i]=(a[i-1]*i)%md;
}
ll n;
while(scanf("%lld",&n)!=EOF){
if(n<=md){
printf("%lld\n",a[n]);
}
else{
printf("0\n");
}
}
return 0;
}
Keen On Everything But Triangle
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Problem Description
N sticks are arranged in a row, and their lengths are a1,a2,...,aN.
There are Q querys. For i-th of them, you can only use sticks between li-th to ri-th. Please output the maximum circumference of all the triangles that you can make with these sticks, or print −1 denoting no triangles you can make.
InputThere are multiple test cases.
Each case starts with a line containing two positive integers N,Q(N,Q≤105).
The second line contains N integers, the i-th integer ai(1≤ai≤109) of them showing the length of the i-th stick.
Then follow Q lines. i-th of them contains two integers li,ri(1≤li≤ri≤N), meaning that you can only use sticks between li-th to ri-th.
It is guaranteed that the sum of Ns and the sum of Qs in all test cases are both no larger than 4×105.
OutputFor each test case, output Q lines, each containing an integer denoting the maximum circumference.
Sample Input
5 3 2 5 6 5 2 1 3 2 4 2 5
Sample Output
13 16 16
签到题，首先考虑区间最大的三个数能否形成三角形，如果不能，考虑区间第二大、第三大、第四大的三个数，以此类推，直到能形成三角形，用主席树维护一下就好了。由三角形最小的两条边大于第三边的性质可知，只需要考虑区间的前 大数即可（最坏情况下区间前几大数形成了斐波那契数列）。
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
#define ls i << 1
#define rs i << 1 + 1
typedef long long ll;
const int maxn=(int)1e5+100;
const int M=maxn*30;
int n,q;
inline int read(){
int x = 0;
char c = getchar();
bool flag = 0;
while(!isdigit(c)) {
if(c == '-')
flag = 1;
c = getchar();
}
while(isdigit(c)) {
x = (x << 3) + (x << 1) + (c ^ 48);
c = getchar();
}
return flag ? -x : x;
}
inline void write(ll x){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
}
int T[maxn];
int lson[M],rson[M],c[M];
int X[maxn],K[maxn];
int cnt = 0,en;
int build(int l,int r){
int root = cnt ++;
c[root] = 0;
if(l != r){
int mid = (l + r) >> 1;
lson[root] = build(l,mid);
rson[root] = build(mid + 1,r);
}
return root;
}
int update(int root,int pos,int val){
int newroot = cnt ++,tmp = newroot;
c[newroot] = c[root] + val;
int l = 1,r = en;
while(l < r){
int mid = (l + r) >> 1;
if(pos <= mid){
lson[newroot] = cnt ++;
rson[newroot] = rson[root];
newroot = lson[newroot];
root = lson[root];
r = mid;
}
else {
rson[newroot] = cnt ++;
lson[newroot] = lson[root];
newroot = rson[newroot];
root = rson[root];
l = mid + 1;
}
c[newroot] = c[root] + val;
}
return tmp;
}
int query(int lroot,int rroot,int k){
int l = 1,r = en;
while(l < r){
int mid = (l + r) >> 1;
if(c[lson[rroot]] - c[lson[lroot]] >= k){
r = mid;
lroot = lson[lroot];
rroot = lson[rroot];
}
else {
l = mid + 1;
k -= c[lson[rroot]] - c[lson[lroot]];
rroot = rson[rroot];
lroot = rson[lroot];
}
}
return l;
}
void solve(){
cnt=0;
rep(i,1,n){
K[i]=read(); X[i] = K[i];
//scanf("%d",&K[i]); X[i] = K[i];
} sort(X+1,X+1+n);
en = unique(X + 1,X + 1 + n) - X - 1;
T[0] = build(1,en);
rep(i,1,n){
int pos = lower_bound(X + 1,X + 1 + en,K[i]) - X;
T[i] = update(T[i - 1],pos,1);
}
while(q--){
int l,r;l=read();r=read(); //scanf("%d%d",&l,&r);
int k=r-l+1,flag=0;
if(k<3){printf("-1\n");continue;}
int a=X[query(T[l-1],T[r],k)],b=X[query(T[l-1],T[r],k-1)],c=X[query(T[l-1],T[r],k-2)];
k-=3;
rep(i,1,50){
if(b+c>a){write(1ll*a+1ll*b+1ll*c);puts("");flag=1;break;}
else{
a=b;b=c;c=X[query(T[l-1],T[r],k)];k--;
}
if(k<0) break;
}
if(!flag) puts("-1");
}
}
int main() {
while(~scanf("%d%d",&n,&q)) solve();
}
Longest Subarray
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Problem Description
You are given two integers C,K and an array of N integers a1,a2,...,aN. It is guaranteed that the value of ai is between 1 to C.
We define that a continuous subsequence al,al+1,...,ar(l≤r) of array a is a good subarray if and only if the following condition is met:
∀x∈[1,C],∑i=lr[ai=x]=0or∑i=lr[ai=x]≥K
It implies that if a number appears in the subarray, it will appear no less than K times.
You should find the longest good subarray and output its length. Or you should print 0 if you cannot find any.
InputThere are multiple test cases.
Each case starts with a line containing three positive integers N,C,K(N,C,K≤105).
The second line contains N integer a1,a2,...,aN(1≤ai≤C).
We guarantee that the sum of Ns, the sum of Cs and the sum of Ks in all test cases are all no larger than 5×105.
OutputFor each test case, output one line containing an integer denoting the length of the longest good subarray.
Sample Input
7 4 2 2 1 4 1 4 3 2
Sample Output
4
如果右端点固定，对于每种元素，可行的左端点下标是两段连续的区间。对于每种元素，将它的可行左端点区间在线段树中加一。当右端点右移的时候，维护c种元素的可行左端点。查询时只需要询问线段树中最小的、值为c的下标即可。
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define rep(i, a, b) for(int i = (a); i < (b); ++i)
#define sz(a) (int)a.size()
typedef long long ll;
typedef vector<int> vi;
const int N = 101010;
int n, C, k;
vi vec[N];
struct Seg {
#define ls rt << 1
#define rs ls | 1
static const int N = ::N << 2;
int ma[N], la[N], pos[N];
void gao(int rt, int c) {
ma[rt] += c; la[rt] += c;
}
void down(int rt) {
if(!la[rt]) return ;
gao(ls, la[rt]);
gao(rs, la[rt]);
la[rt] = 0;
}
void up(int rt) {
ma[rt] = max(ma[ls], ma[rs]);
pos[rt] = (ma[rt] == ma[ls] ? pos[ls] : pos[rs]);
}
void build(int l, int r, int rt) {
ma[rt] = la[rt] = 0, pos[rt] = l;
if(l == r) return ;
int mid = l + r >> 1;
build(l, mid, ls);
build(mid + 1, r, rs);
}
void upd(int L, int R, int c, int l, int r, int rt) {
if(L > R) return ;
if(L <= l && r <= R) {
gao(rt, c);
return ;
}
int mid = l + r >> 1;
down(rt);
if(L <= mid) upd(L, R, c, l, mid, ls);
if(R > mid) upd(L, R, c, mid + 1, r, rs);
up(rt);
}
int qry(int L, int R, int l, int r, int rt) {
if(ma[rt] != C) return 0;
if(L <= l && r <= R) return pos[rt];
int mid = l + r >> 1;
down(rt);
if(L <= mid) {
int t = qry(L, R, l, mid, ls);
if(t) return t;
}
if(R > mid) return qry(L, R, mid + 1, r, rs);
return 0;
}
}seg;
int main() {
while(cin >> n >> C >> k) {
rep(i, 1, C + 1) vec[i].clear(), vec[i].pb(0);
int ans = 0;
seg.build(1, n, 1);
rep(i, 1, n + 1) {
int c; cin >> c;
seg.upd(i, i, C - 1, 1, n, 1);
seg.upd(vec[c].back() + 1, i - 1, -1, 1, n, 1);
vec[c].pb(i);
int p = sz(vec[c]) - k - 1;
if(p >= 0) seg.upd(vec[c][p] + 1, vec[c][p + 1], 1, 1, n, 1);
int j = seg.qry(1, i, 1, n, 1); if(!j) continue;
ans = max(ans, i - j + 1);
}
cout << ans << endl;
}
return 0;
}
