- 1IntelliJ IDEA 4 新特性 之 On-the-Fly Code Analysis(动态代码分析)_on-the-fly code analysis怎么用
- 2深度学习系列56：使用whisper进行语音转文字_faster-whisper加速
- 3华为桌面云解决方案概述_解决方案概述和数据安全建议
- 4cmd命令之Xcopy介绍_复制文件夹里所有文件到另一个文件夹操作方式
- 5C++学习笔记——Eigen模块（用于矩阵运算）_c++ eigen
- 6基于vue-simple-uploader的文件分片上传_vue-simple-uploader配置categorymap
- 7洛谷B2095 白细胞计数
- 82021年中国企业直播行业发展回顾及未来预测分析[图]_直播间前五年收入预测
- 9Hive映射Hbase_hive hbase 映射表
- 10DOS 字符和符号_dos 通配符
第 45 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（银川），签到题5题_graduation season is approaching and it's time to
赞
踩
补题链接：https://codeforces.com/gym/104022
A.Best Player
A. Best Player
time limit per test2 seconds
memory limit per test512 megabytes
inputstandard input
outputstandard output
Though Bob has finally returned to the college, he has to stay in his dorm with the other three roommates. Don’t know who proposes.
“Let’s play a game!”
It was meant to be light-hearted, and the rules are as follows:
A roommate is designated in turn, and he writes down on paper the coordinates of n points in three-dimensional Euclidean space.
Each of the other roommates selects one of the X-axis, the Y-axis, and the Z-axis, but no two of them make the same choice. After that, each of them counts the number of points after projecting all written points along the direction of the chosen axis. Under the projection, some points may not be distinguishable. Points (1,2,1) and (1,2,5) projected along the direction of the Z-axis, for instance, are not distinguishable.
The roommate with the most points counted will win the game. In case of a tie, the one with the most points counted whose selected axis has the smallest character in the alphabetical order will be the winner. Note that in the alphabetical order X is less than Y, Y is less than Z, and by transitivity, X is less than Z.
Bob does want to win.
“Please help me; I entreat you.”
Add flowers to brocade people, all over finish is; Give timely assistance and have several people?
Input
The first line contains an integer n (1≤n≤100).
In the next n lines, each line contains three integers x, y and z (−100≤x,y,z≤100), representing a three-dimensional point at (x,y,z).
Output
Output a character t (t∈{X,Y,Z}) in a line indicating that the winner’s choice is the t-axis. Note that the output characters are case-sensitive.
Examples
inputCopy
2
1 1 1
1 2 1
outputCopy
X
inputCopy
3
1 2 9
1 2 2
2 2 9
outputCopy
Y
inputCopy
4
-100 -100 100
-100 100 100
100 -100 100
100 100 100
outputCopy
Z
题意：
- 给出三维空间中的n个点，你可以选择从X, Y, Z三个视角中的一个去看（有些点会重合）
- 求能看到的点数最多的视角是哪个，输出{X,Y,Z}
思路：
- 对于X方向，当且仅当{Y,Z}对相等时重合，个数不累加。 YZ方向同理。
- 因此开个三个map维护一下对应的对数，然后输出size最大的那个方向即可。
#include<bits/stdc++.h>
using namespace std;
int main(){
int n; cin>>n;
map<pair<int,int>, int>mx;
map<pair<int,int>, int>my;
map<pair<int,int>, int>mz;
for(int i = 1; i <= n; i++){
int x, y, z; cin>>x>>y>>z;
mx[{y,z}]++;
my[{x,z}]++;
mz[{x,y}]++;
}
int mm = max({mx.size(), my.size(), mz.size()});
if(mm==mx.size())cout<<"X";
else if(mm==my.size())cout<<"Y";
else if(mm==mz.size())cout<<"Z";
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
E.Isomerism
E. Isomerism
time limit per test1 second
memory limit per test512 megabytes
inputstandard input
outputstandard output
In chemistry, isomerism is the phenomenon in which more than one compounds have the same chemical formula but different chemical structures. Chemical compounds that have identical chemical formulae but differ in properties and the arrangement of atoms in the molecule are called isomers.
Ethylene, which has a carbon-carbon double bond, is one of the most important fundamental chemicals in the petrochemical industry as it is the source material for a variety of products such as polyethene resin, ethylene glycol, vinyl chloride resin, acetic acid, styrene, and alpha-olefin which are produced by polymerization, oxidation, alkylation, hydration, or the addition of halogen. The precise format of an ethylene derivative is given in the figure below, where R1,R2,R3,R4 are atoms or atomic groups. We always suppose that R1 and R2 are on the same side of the carbon-carbon double bond, while R3 and R4 are on the other side. The carbon-carbon double bond in an ethylene derivative cannot rotate around the bond axis.
To distinguish isomers of the ethylene derivatives, two different naming methods, say Cis-Trans isomerism and Zasammen-Entgegen isomerism, are invented in the academic circle. The different scopes of application between these two methods are listed as follows:
If a carbon atom connects with two identical atoms or atomic groups, isomerism of the given ethylene derivative does not exist; otherwise
if some atoms or atomic groups connecting with carbon atoms are the same, the ethylene derivative is called Cis-Trans isomerism. If the two identical atoms or atomic groups lie on the same side (i.e. upside or downside in the figure above) of the carbon-carbon double bond, it is called Cis-isomerism, or else it is called Trans-isomerism;
if the four atoms or atomic groups connecting with carbon atoms are pairwise distinct, the ethylene derivative is called Zasammen-Entgegen isomerism. If the atom or the atomic group of R1 and R3 with a higher priority and the atom or the atomic group of R2 and R4 with a higher priority lie on the same side (i.e. upside or downside in the figure above) of the carbon-carbon double bond, it is called Zasamman-isomerism, or else it is called Entgegen-isomerism.
All the atoms or atomic groups which may appear in R1, R2, R3 and R4 are listed as follows in descending order of the priority, the first of which is the one with the highest priority.
-F, -Cl, -Br, -I, -CH3, -CH2CH3, -CH2CH2CH3, -H
Now, you are asked to determine if there is any isomerism for a given ethylene derivative and find out the naming method it fits for when possible.
Input
The first line contains an integer T (1≤T≤105), indicating the number of test cases.
Then follow T test cases. For each test case:
The only line contains four strings R1, R2, R3 and R4 (R1,R2,R3,R4∈{-F, -Cl, -Br, -I, -CH3, -CH2CH3, -CH2CH2CH3, -H}), which are the atoms or atomic groups connecting to carbon atoms of the ethylene derivative.
Output
For each test case, output a string in one line, describing the type of isomerism the ethylene derivative fits for as follows:
If there is no isomerism of this ethylene derivative, output “None”;
If it is Cis-isomerism, output “Cis”;
If it is Trans-isomerism, output “Trans”;
If it is Zasamman-isomerism, output “Zasamman”;
Otherwise, it should be Entgegen-isomerism, so output “Entgegen”.
Example
inputCopy
2
-H -H -H -Cl
-F -F -Br -Cl
outputCopy
None
Cis
题意：
- T组数据（1e5），每次给出4个字符串，代表碳-碳双键周围的 4 个原子团。
- 原子团的可能取值按优先度从高到低为： -F、-Cl、-Br、-I、-CH3、-CH2CH3、-CH2CH2CH3、-H。
- 根据性质输出：
一个碳原子与两个相同的原子团相连，则输出 None。
两个相同的原子团位于碳-碳双键的同一侧（即图中的上侧或下侧），则输出 Cis
两个相同的原子团位于碳-碳双键的不同侧（即图中的上左或右侧），则输出 Trans
R1和R3中具有较高优先级的的原子团 与 R2 和 R4 中具有较高优先级的的原子团位于碳-碳双键的同一侧，则输出 Zasamman.
R1和R3中具有较高优先级的的原子团 与 R2 和 R4 中具有较高优先级的的原子团位于碳-碳双键的不同侧，则输出Entgegen
思路：
- 前3种情况都可以直接判断。
R1=R3 || R2=R4，输出None
R1=R2 || R3=R4，输出Cis
R1=R4 || R2=R3，输出Trans - 对于最后两种情况，分别取max{R1, R3}和max{R2,R4}进行比较。
#include<bits/stdc++.h>
using namespace std;
int main(){
string kk[] = {"-F", "-Cl", "-Br", "-I", "-CH3", "-CH2CH3", "-CH2CH2CH3", "-H"};
map<string, int>rk;
for(int i = 0; i < 8; i++)rk[kk[i]] = i;
int T; cin>>T;
while(T--){
string R1, R2, R3, R4; cin>>R1>>R2>>R3>>R4;
if(R1==R3 || R2==R4)cout<<"None\n";
else if(R1==R2 || R3==R4)cout<<"Cis\n";
else if(R1==R4 || R2==R3)cout<<"Trans\n";
else{
if(rk[R1] < rk[R3] && rk[R2] < rk[R4])cout<<"Zasamman\n";
else if(rk[R1] > rk[R3] && rk[R2] > rk[R4])cout<<"Zasamman\n";
else{
cout<<"Entgegen\n";
}
}
}
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
J.Let’s Play Jigsaw Puzzles!
J. Let’s Play Jigsaw Puzzles!
time limit per test4 seconds
memory limit per test512 megabytes
inputstandard input
outputstandard output
Bob bought a new jigsaw puzzle yesterday. The puzzle consists of m2 rectangular pieces, where each piece contains a unique number ranged from 1 to m2 used for identification and four associated numbers indicating the adjacent pieces.
Specifically, the piece numbered i is described with four numbers ni, si, wi and ei, corresponding to four adjacent pieces: the piece numbered ni (resp., si, wi and ei) lie on the north side (resp., south side, west side and east side). If an associated number is −1, no more piece would lie on the corresponding side.
Undoubtedly, the goal of this game is to arrange all pieces in the correct locations. The instruction says that the complete image is square, with m rows and m columns.
At this juncture, Bob is at the International Collegiate Programming Contest in Yinchuan. He has no time to solve the jigsaw puzzle but has to solve Problem K instead. Can you help him?
Input
The first line contains an integer m (1≤m≤103).
In the next m2 lines, the i-th line contains four integers ni, si, wi and ei (ni,si,wi,ei∈{−1}∪[1,m2]). It is guaranteed that a corresponding solution does exist.
Output
Output a sorted jigsaw puzzle in m lines from north to south, where each line contains m integers representing the pieces from west to east in the corresponding row of the jigsaw puzzle.
Example
inputCopy
2
-1 3 -1 2
-1 4 1 -1
1 -1 -1 4
2 -1 3 -1
outputCopy
1 2
3 4
题意：
- 有一个m*m的矩阵，被拆分为m*m个拼图，给出数字i对应的拼图（一行四个数，分别表示这块拼图的上下左右四个方向的数字，没有数字就是-1）。
- 求原本的矩阵并输出。
思路：
- 开始没看到第i行代表的就是数字i的拼图，于是写了个bfs根据四个顶点的数字往外面跑。
但是WA了，然后发现等于3的时候的123456789是跑不出解的，然而题目并没有给出无解的情况，才意识到题目的给的其实是数字i的拼图。 - 不过bfs加个特判和奇数的情况也可以过。
//bfs
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2020;
int u[maxn*maxn], d[maxn*maxn], l[maxn*maxn], r[maxn*maxn];
int uu[maxn*maxn], dd[maxn*maxn], ll[maxn*maxn], rr[maxn*maxn]; //维护i点四个方向点位信息
int a[maxn][maxn];
struct node{ int x, y, v; };
int dx[] = {-1,1,0,0};
int dy[] = {0,0,-1,1};
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int m; cin>>m;
if(m==1){ cout<<"1\n"; return 0;}
queue<node>q;
for(int i = 1; i <= m*m; i++){
cin>>u[i]>>d[i]>>l[i]>>r[i];
if(u[i]!=-1)dd[u[i]] = i; //值为u[i], 下面的元素是第几个
if(d[i]!=-1)uu[d[i]] = i;
if(l[i]!=-1)rr[l[i]] = i;
if(r[i]!=-1)ll[r[i]] = i;
if(u[i]==-1 && l[i]==-1){ a[1][1] = i; a[1][2] = r[i]; a[2][1] = d[i]; q.push({1,2,r[i]}); q.push({2,1,d[i]}); q.push({1,1,i}); }
if(r[i]==-1 && u[i]==-1){ a[1][m] = i; a[1][m-1] = l[i]; a[2][m] = d[i]; q.push({1,m-1,l[i]}); q.push({2,m,d[i]}); q.push({1,m,i}); }
if(r[i]==-1 && d[i]==-1){ a[m][m] = i;}
}
for(int i = 0; i <= m+1; i++)a[0][i] = a[m+1][i] = a[i][0] = a[i][m+1] = 1;
auto func = [&](int ox, int oy, int x, int y, int t){
if(x<=0 || y<=0 || x>=m || y>=m)return ;
for(int i = 0; i < 4; i++){
int nx = x+dx[i], ny = y+dy[i];
if(nx==ox && ny == oy)continue;
if(a[nx][ny]==0){
if(i==0 && u[t]!=-1){a[nx][ny] = u[t]; q.push({nx, ny, u[t]});}
if(i==1 && d[t]!=-1){a[nx][ny] = d[t]; q.push({nx, ny, d[t]});}
if(i==2 && l[t]!=-1){a[nx][ny] = l[t]; q.push({nx, ny, l[t]});}
if(i==3 && r[t]!=-1){a[nx][ny] = r[t]; q.push({nx, ny, r[t]});}
}
}
};
while(q.size()){
int x = q.front().x, y = q.front().y, v = q.front().v; q.pop();
if(uu[v] != 0)func(x, y, x-1, y, uu[v]);
if(dd[v] != 0)func(x, y, x+1, y, dd[v]);
if(ll[v] != 0)func(x, y, x, y-1, ll[v]);
if(rr[v] != 0)func(x, y, x, y+1, rr[v]);
}
for(int i = 1; i <= m; i++){
for(int j = 1; j <= m; j++){
cout<<a[i][j]<<" \n"[j==m];
}
}
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 不过其实题目有这个性质的话，本来就有更简单的做法，首先还是一样先确定四个角落的位置。
然后我们只需要遍历所有已经确定位置的块（按层递推即可），将与之相邻的块（下一层的块）也放进表示地图的二维数组中。就可以在m*m的时间里跑出来。 - 正确性也不难证明，因为数字是不重复的，每个拼图也必定是唯一的，如果知道了以一层的数字，每个数字的表示下方的数组存的就是下一层的数字。
//直接递推
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2020;
int u[maxn*maxn], d[maxn*maxn], l[maxn*maxn], r[maxn*maxn];
int a[maxn][maxn];
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int m; cin>>m;
for(int i = 1; i <= m*m; i++){
cin>>u[i]>>d[i]>>l[i]>>r[i];
if(u[i]==-1 && l[i]==-1)a[1][1] = i;
}
for(int i = 2; i <= m; i++)a[1][i] = r[a[1][i-1]];
for(int i = 2; i <= m; i++){
for(int j = 1; j <= m; j++){
a[i][j] = d[a[i-1][j]];
}
}
for(int i = 1; i <= m; i++){
for(int j = 1; j <= m; j++){
cout<<a[i][j]<<" \n"[j==m];
}
}
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
K.Browser Games
K. Browser Games
time limit per test2 seconds
memory limit per test512 megabytes
inputstandard input
outputstandard output
In the upcoming n days, n browser games will be released on a new website. According to the plan, the administrator will release a new game per day. Users have to open the corresponding URL (Uniform Resource Locator) and get feedback from the server to download a game.
However, the setup of the server uses unreadable legacy codes. Once a user somehow finds the URL of an unreleased game, the data of the game would leak out. To temporarily fix the problem, the administrator decided to add a series of confirmation prefixes, which are non-empty strings, at the server-side. The server will respond with the correct game data when the requested URL does correspond to a game (no matter released or unreleased) and at least one confirmation prefix is a prefix of the URL; otherwise, the server will declare that the game is not found.
To make the work easier, the administrator asks you to find the minimum number of confirmation prefixes the server required to avoid data leaks every time after a new game release.
Input
The first line contains an integer n (1≤n≤5×104), indicating the number of browser games to be released.
In the next n lines, the i-th line contains a non-empty string, consisting of only lowercase letters (‘a’ to ‘z’), dots (‘.’) and forward slashes (‘/’), indicating the URL of the browser game released on the i-th day.
It is guaranteed that the length of each given URL is at most 50, and no given URL is the prefix of any other given URL.
Output
Output n lines, the i-th of which contains an integer indicating the minimum number of required confirmation prefixes after the i-th new game released.
Example
inputCopy
3
ufoipv.ofu
hsbocmvfgboubtz.kq
hfotijo.njipzp.dpn/kb
outputCopy
1
2
2
题意：
-
n个字符串si, 求第i个串前面（不包含i）的字符串集合，能够唯一匹配这些串（且不能被后面的字符串匹配）的前缀个数。
-
对于样例
ufoipv.ofu， 需要区分，只需要1个u即可。
hsbocmvfgboubtz.kq，需要一个u和一个hs即可。
hfotijo.njipzp.dpn/kb，需要一个u和一个h即可。
所以为122 -
如果样例为
ufoipv.ofu， 需要一个u
hfotijo.njipzp.dpn/kb，需要一个u和一个hf
hsbocmvfgboubtz.kq，需要一个u和一个hf和一个hs
hcbocmvfgboubtz.kq，需要一个u和一个h即可
所以为1232
思路：
- 因为URL的长度不超过50，同时个数只有5e4。所以我们暴力处理出所有输入的字符串的前缀，也只有2e6个，然后字符串哈希成数字，维护出现的个数。
- 再按顺序跑一遍，对于当前串，遇到的前缀（包括之前的串）都从数组中删除，直到出现某个前缀数组中不存在为止 （即后面的串里都不包含这个前缀）。
- 再开一个数组前面使用的串中包含pre的串的个数（hf, hs, h），则每次的答案为res-前面的hf,hs，加上本次的h。然后更新这个数组。
//字符串哈希
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 10000000000123207;
const int base = 131;
const int maxn = 1e5+10;
string s[maxn];
unordered_map<int, int> mp(maxn * 50);
unordered_map<int, int> st(maxn * 50);
signed main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n; cin>>n;
for(int i = 1; i <= n; i++){
cin>>s[i];
int pre = 0;
for(char ch : s[i]){
pre = (pre*base+ch)%mod;
mp[pre]++;
}
}
int res = 0;
for(int i = 1; i <= n; i++){
int pre = 0;
for(char ch : s[i]){
pre = (pre*base+ch)%mod;
mp[pre]--;
if(mp[pre]==0)mp.erase(pre);
if(!mp.count(pre))break; //后面的都不包含
}
int cnt = st[pre]; //前面使用的串中包含pre的串的个数（hf, hs, h）
res = res-cnt+1;
cout<<res<<"\n";
pre = 0;
for(char ch : s[i]){
pre = (pre*base+ch)%mod;
st[pre]++; //将s[i]累积上去
st[pre] -= cnt; //去掉使用的串不算
}
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 或者也可以字典树，先跑一遍将所有的字符串都加入字典树，打上标记1。
- 然后逆序查找字典树，给每个节点打上2标记。对于当前字符串的一个节点i，如果他的标记是1，那么代表他以及他的子树都是前缀的，并且不在后缀里，直接累加答案+1即可。如果标记为2，证明后面有这个串，因为不能包含后面，所以还要继续往下找。
- 或者也可以正序查找，每次将查到的前缀都删除，如果一个前缀没有了，证明后面的串里没有这个前缀。
//字典树
#include<bits/stdc++.h>
using namespace std;
const int maxn = 3e6+10;
int ans = 0;
int tire[maxn][30], tot = 0, sum[maxn], sum2[maxn];
int getid(char x){ return x=='.' ? 26 : (x=='/' ? 27 : x-'a'); }
void insert(string s){
int now = 0;
for(int i = 0; i < s.size(); i++){
int id = getid(s[i]);
if(tire[now][id]==0)tire[now][id] = ++tot;
sum[tire[now][id]]++;
now = tire[now][id];
}
}
void find(string s){
int now = 0;
vector<int>p;
for(int i = 0; i < s.size(); i++){
int id = getid(s[i]);
sum[tire[now][id]]--;
if(sum[tire[now][id]]==0){ //后面的串没有这个前缀
int cnt = 1-sum2[tire[now][id]]; //改变量
ans += cnt;
for(int j = 0; j < p.size(); j++){
sum2[p[j]] += cnt; //回溯
}
return ;
}
now = tire[now][id];
p.push_back(now);
}
}
int main(){
int n; cin>>n;
vector<string>vc;
for(int i = 0; i < n; i++){
string s; cin>>s;
vc.push_back(s);
insert(s);
}
for(int i = 0; i < n; i++){
find(vc[i]);
cout<<ans<<"\n";
}
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
G.Photograph
G. Photograph
time limit per test1 second
memory limit per test512 megabytes
inputstandard input
outputstandard output
Graduation season is approaching and it’s time to take commemorative photos.
There are n students in Bob’s class, each assigned with a unique student number from 1 to n, where the height of the student numbered i is hi. They want to take photos at the school gate and q more memorable places. For each place, students will arrive in a known order, and, as they hope for more personal engagement, once a student arrived they take a new photo so that n photos will be taken. After finishing all the n photos at the place, students will go back to their dorms and set up a new time for the next place.
To make the queue orderly, every time students have to stand in a row in ascending order of their student numbers when taking a new photo, and the orderliness of the photo is defined as the sum of the squares of the height differences between every two neighbouring students in the row. Your task is to, for each place, calculate the sum of the orderlinesses of all the n photos that are taken there.
Input
The first line contains two integers n and q (1≤n≤105,0≤q≤100), indicating the number of students and the number of memorable places.
The second line contains n integers indicating the heights of students, the i-th of which is hi (1≤hi≤104).
The third line contains n pairwise distinct integers p1,p2,…,pn, ranged from 1 to n, representing the student numbers in the order of their attendance at the school gate.
In the next q lines, the i-th line contains an integer k (0≤k≤109), which says that the order of attendance for students at the (i+1)-th place is rescheduled from the previous order by shifting left (k+lastans) times, where the lastans is the sum of the orderlinesses of the n photos taken at the i-th place.
Note that the order p1,p2,…,pn−1,pn after shifting left once will turn to the new order p2,p3,…,pn,p1.
Output
Output (q+1) lines, where the i-th line contains an integer representing the sum of the orderlinesses of the n photos taken at the i-th place.
Example
inputCopy
5 4
1 2 3 4 5
1 2 3 4 5
6
6
8
10
outputCopy
10
10
13
21
36
Note
For the sample case, the order of students’ attendance at each place are listed as follows:
[1,2,3,4,5] →[2,3,4,5,1] →[3,4,5,1,2] →[4,5,1,2,3] →[5,1,2,3,4].
题意：
- 有n个学生，学号分别为1-n,身高为h1-hn。有q+1个地点，每个学生都在每个地点拍一张照片。共n(q+1)张。
- 对于第0个地点，n个学生的到达顺序为p1-pn。在前往第i+1个地点时，学生的到达顺序将会变为到达第i个地点的顺序向左轮换ansi（上一个地点的分数）+ki（题目给出）次之后的结果。
- 每张照片的分数定义为：照片上的学生按学号排序后，相邻两个人的身高差的平方之和。
第i个地点的分数定义为这个地点的n张照片的分数之和。 - 输出q+1个地点的分数。
思路：
- 对于到达本次地点的顺序，可以根据上次的分数+ki按照规则直接求出。
- 知道顺序后，怎么求分数之和呢。比如某个学生j到达后，怎么知道他左右两边的人？直接插入显然是会超时的。
我们可以考虑倒着做，即假设n个人都到了，排个序得到最终的顺序。然后按pn-p1的顺序离场，每个人离场前都拍一张照片，这样就可以数组维护每个人当前左侧和右侧的人是谁，并用双端队列辅助更新。 - 对于分数，当前照片的分数 = 上一张照片的分数 - j和左右两边的人一起产生的贡献 + j左边的人和右边的人产生的贡献。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e5+10;
LL n, q, h[maxn], p[maxn];
LL l[maxn], r[maxn], np[maxn], pre[maxn], nxt[maxn];
LL getans(LL k){
//move
for(int i = 1; i <= n; i++){
l[i] = i-1; r[i] = i+1; //最后按学号排序站
if(i<=k)np[i-k+n] = p[i]; //本次达到的顺序np
else np[i-k] = p[i];
}
r[n] = 0;
//calc, 最后都排好序时sum=n
for(int i = n; i >= 1; i--){ //n个人逐个离场
p[i] = np[i];
pre[p[i]] = l[p[i]]; //维护学号为p[i]的人离场（到达）时左右两边的人的学号
nxt[p[i]] = r[p[i]];
//删掉学号为p[i]的人
r[l[p[i]]] = r[p[i]];
l[r[p[i]]] = l[p[i]];
}
LL ans = 0, sum = 0;
for(int i = 1; i <= n; i++){ //n个人逐个进场
int t = p[i];
if(pre[t]&&nxt[t])sum-=(h[pre[t]]-h[nxt[t]])*(h[pre[t]]-h[nxt[t]]);
if(pre[t])sum+=(h[t]-h[pre[t]])*(h[t]-h[pre[t]]);
if(nxt[t])sum+=(h[t]-h[nxt[t]])*(h[t]-h[nxt[t]]);
ans += sum;
}
return ans;
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>q;
for(int i = 1; i <= n; i++)cin>>h[i];
for(int i = 1; i <= n; i++)cin>>p[i];
LL ans = getans(0);
cout<<ans<<"\n";
for(int i = 1; i <= q; i++){
LL k; cin>>k;
ans = getans((ans+k)%n);
cout<<ans<<"\n";
}
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
