publicstaticvoidmain(String... args)throws Exception { PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out)); BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("./input.txt"))); long N = Long.valueOf(br.readLine()); // (a+a+n-1)*n/2 = N ==> 2a = 2N/n + 1 - n // 枚举2N的所有因子 long x = 2*N; HashSet<Long> set = new HashSet<>(); //i*i大于x那么i之前肯定已经被加入了 for (long i = 1; i*i <= x; i++) { if ((x%i) == 0) { set.add(i); set.add(x/i); } } long res = 0; for (Long f : set) { if ((x/f+1-f)%2==0) res++; } out.println(res); out.flush(); } }
There are $N$ kinds of magical gems, numbered $1, 2, \ldots, N$, distributed in the AtCoder Kingdom.
Takahashi is trying to make an ornament by arranging gems in a row.
For some pairs of gems, we can put the two gems next to each other; for other pairs, we cannot. We have $M$ pairs for which the two gems can be adjacent: (Gem $A_1$, Gem $B_1$), (Gem $A_2$, Gem $B_2$), $\ldots$, (Gem $A_M$, Gem $B_M$). For the other pairs, the two gems cannot be adjacent. (Order does not matter in these pairs.)
Determine whether it is possible to form a sequence of gems that has one or more gems of each of the kinds $C_1, C_2, \dots, C_K$. If the answer is yes, find the minimum number of stones needed to form such a sequence.
publicstaticvoidmain(String... args)throws Exception { PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out)); BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("./input.txt"))); int[] in = read(br); int N = in[0], M = in[1]; int INF = 0x3f3f3f3f; List<Integer>[] adj = new ArrayList[N]; for (int i = 0; i < M; i++) { int[] t = read(br); int x = t[0]-1, y = t[1]-1; if (adj[x] == null) { adj[x] = new ArrayList<>(); } if (adj[y] == null) { adj[y] = new ArrayList<>(); } adj[x].add(y); adj[y].add(x); } int K = read(br)[0]; int[] C = read(br); HashMap<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < K; i++) map.put(--C[i], i); //K个关键点之间的最短距离 int[][] dis = newint[K][K]; Queue<int[]> queue = new LinkedList<>(); for (int i = 0; i < K; i++) { Arrays.fill(dis[i], INF); queue.clear(); queue.add(newint[]{C[i], 0}); boolean[] vis = newboolean[N]; while (!queue.isEmpty()) { int[] cur = queue.poll(); if (map.containsKey(cur[0])) { dis[i][map.get(cur[0])] = cur[1]; } if (adj[cur[0]] == null) continue; for (Integer next : adj[cur[0]]) { if (vis[next]) continue; queue.add(newint[]{next, cur[1]+1}); vis[next] = true; } } } int[][] dp = newint[1<<K][K]; for (int i = 0; i < (1<<K); i++) { Arrays.fill(dp[i], INF); } for (int i = 0; i < K; i++) { dp[1<<i][i] = 1; } //枚举所有状态递推 for (int mask = 0; mask < (1<<K); mask++) { for (int i = 0; i < K; i++) { //C[i]被选取，C[j]未被选取（因为有INF的原因，判断去掉也可AC，不过最好还是加上） if ((mask&(1<<i))==0) continue; for (int j = 0; j < K; j++) { if ((mask&(1<<j))==1 || dis[i][j] == INF || dp[mask][i] == INF) continue; dp[mask|(1<<j)][j] = Math.min(dp[mask|(1<<j)][j], dp[mask][i] + dis[i][j]); } } } int res = INF; for (int i = 0; i < K; i++) { res = Math.min(res, dp[(1<<K)-1][i]); } if (res == INF) out.println(-1); else out.println(res); out.flush(); }
Given is a sequence $A = [a_0, a_1, a_2, \dots, a_{N-1}]$ that is a permutation of $0, 1, 2, \dots, N - 1$.
For each $k = 0, 1, 2, \dots, N - 1$, find the inversion number of the sequence $B = [b_0, b_1, b_2, \dots, b_{N-1}]$ defined as $b_i = a_{i+k \bmod N}$.
Constraints
All values in input are integers.
$2≤N≤3×10^5$
$a_0,a_1,a_2,…,a_{N−1}$ is a permutation of $0,1,2,…,N−1$.
Sample Input 1
4 0123
Sample Output 1
0 3 4 3
We have $A = [0, 1, 2, 3]$.
For $k = 0$, the inversion number of $B = [0, 1, 2, 3]$ is $0$.
For $k = 1$, the inversion number of $B = [1, 2, 3, 0]$ is $3$.
For $k = 2$, the inversion number of $B = [2, 3, 0, 1]$ is $4$.
For $k = 3$, the inversion number of $B = [3, 0, 1, 2]$ is $3$.
//q[1001] = t[1001] + t[1000] publicstaticintquery(int i){ int res = 0; while (i > 0) { res += tree[i]; i -= lowbit(i); } return res; }
publicstaticvoidadd(int i, int val){ while (i < tree.length) { tree[i] += val; i += lowbit(i); } }
publicstaticvoidmain(String... args)throws Exception { PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out)); BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("./input.txt"))); int N = read(br)[0]; int[] A = read(br); tree = newint[N+1]; //这题不用离散化，序列值就是Rank long res = 0; //树状数组或者归并都可 for (int i = N-1; i >= 0; i--) { add(A[i]+1, 1); res += query(A[i]); } out.println(res); //-k+(N-1-k) = N-1-2*k for (int i = 0; i < N-1; i++) { res += N-1-2*A[i]; out.println(res); } out.flush(); }
//q[1001] = t[1001] + t[1000] publicstaticintquery(int i){ int res = 0; while (i > 0) { res += tree[i]; i -= lowbit(i); } return res; }
publicstaticvoidadd(int i, int val){ while (i < tree.length) { tree[i] += val; i += lowbit(i); } }
publicstaticvoidmain(String... args)throws Exception { PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out)); BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("./input.txt"))); int N = read(br)[0]; int[] A = read(br); tree = newint[N+1]; //离散化（这题不用离散化，为了更加通用） int[][] temp = newint[N][2]; for (int i = 0; i < N; i++) temp[i] = newint[]{A[i], i}; Arrays.sort(temp, (t1, t2)->t1[0]-t2[0]); int[] rank = newint[N]; for (int i = 0; i < N; i++) { rank[temp[i][1]] = i+1; } long res = 0; //树状数组或者归并都可 for (int i = N-1; i >= 0; i--) { add(rank[i], 1); res += query(rank[i]-1); } out.println(res); //改动的地方 for (int i = 0; i < N-1; i++) { res -= query(rank[i]-1); res += query(N) - query(rank[i]); out.println(res); } out.flush(); }
