说在前面
被毒瘤题虐了，看到昨天牛客有普及模拟赛，来vp。
大概花了1h AK。
比赛链接
A
发现做完(n)次操作等于没做，所以做(x)次操作等同于做(x mod n)次操作，然后先输出[x + 1,n]，再输出[1,x]即可。
# include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
char s[N];
int n; long long x;
int main(void)
{
scanf("%d%lld",&n,&x);
scanf("%s",s + 1);
x = x % n;
for(int i = x + 1; i <= n; i++) cout << s[i];
for(int i = 1; i <= x; i++) cout << s[i];
return 0;
}
B
第一眼看上去是个dp。
方便讲解，设(a[i][j])为(a_i)的第(j)个取值。
设(dp[i][j])为以(a[i][j])位置做结尾的最长上升子序列。
易得
[dp[i][j] = max_{i_0 < i,a[i_0][j_0] < a[i][j]} {dp[i_0][j_0]} + 1
]
然后用BIT优化dp即可。
看到提问区有说把值域提到1e9的，其实离散化一下应该也能过。
# include <bits/stdc++.h>
using namespace std;
const int K = 5e3 + 5,N = 1e3 + 5;
int k,n;
int a[N][K];
int Max;
struct BIT
{
int T[N];
int lowbit(int x) {return x & (-x);}
void add(int x,int d)
{
while(x <= Max)
{
T[x] = max(T[x],d);
x += lowbit(x);
}
return;
}
int query(int x)
{
int ans = 0;
while(x)
{
ans = max(ans,T[x]);
x -= lowbit(x);
}
return ans;
}
}T;
int dp[N][K];
int main(void)
{
scanf("%d%d",&k,&n);
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= k; j++)
{
scanf("%d",&a[i][j]);
Max = max(Max,a[i][j]);
}
}
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= k; j++)
{
dp[i][j] = 1;
if(i == 1) T.add(a[i][j],1);
}
}
for(int i = 2; i <= n; i++)
{
for(int j = 1; j <= k; j++)
{
dp[i][j] = max(dp[i][j],T.query(a[i][j] - 1) + 1);
}
for(int j = 1; j <= k; j++)
{
T.add(a[i][j],dp[i][j]);
}
}
int ans = 0;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= k; j++) ans = max(ans,dp[i][j]);
}
printf("%d
",ans);
return 0;
}
C
笑死了，什么傻逼题。
建反图从小到大枚举起点跑dfs，跑的时候记录vis，直到每个点都走过一遍。
# include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n,m;
vector <int> g[N];
bool vis[N];
int total = 0;
int ans[N];
void dfs(int x,int col)
{
++total;
vis[x] = 1;
ans[x] = min(ans[x],col);
if(total == n) return;
for(int i = 0; i < (int)g[x].size(); i++)
{
int v = g[x][i];
if(vis[v]) continue;
dfs(v,col);
}
return;
}
int main(void)
{
scanf("%d%d",&n,&m);
for(int i = 1; i <= m; i++)
{
int u,v; scanf("%d%d",&u,&v);
g[v].push_back(u);
}
for(int i = 1; i <= n; i++) ans[i] = i;
for(int i = 1; i <= n; i++)
{
if(!vis[i] && total < n) dfs(i,i);
}
sort(ans + 1,ans + n + 1);
int L = unique(ans + 1,ans + n + 1) - ans - 1;
for(int i = 1; i <= L; i++) printf("%d ",ans[i]);
return 0;
}
D
不难发现我们可以这样构造吃糖的顺序：
- (n)先入队。
- (n - 1)可以加到队左边或者右边。
- (n - 2)可以加到队左边或者右边。
- (cdots)
- (1)可以加到队左边或者右边。
考虑现在考虑(x)入队，设队列为(b)，(sum = sum {Delta_i})
不难发现，若(x)加入队列左边，则对答案的贡献即为(sum)。
若加入队列右边，则对答案的贡献即为(Delta_x cdot (n - x))。
比较大小判断左右即可。然后最后模拟一遍输出。
我代码里用的deque实现/cy
# include <bits/stdc++.h>
using namespace std;
# define int long long
const int N = 2e5 + 5;
int n,a[N];
int delta[N];
deque <int> q;
int sum;int ans = 0;
signed main(void)
{
scanf("%lld",&n);
for(int i = 1; i <= n; i++)
{
scanf("%lld",&a[i]);
}
for(int i = 1; i <= n; i++)
{
scanf("%lld",&delta[i]);
}
q.push_front(n);
sum = delta[n];
for(int i = n - 1; i >= 1; i--)
{
if(sum > delta[i] * (n - i)) q.push_front(i);
else q.push_back(i);
sum += delta[i];
}
int t = 0;
while(!q.empty())
{
int x = q.front(); q.pop_front();
ans = ans + a[x] + delta[x] * t;
++t;
}
printf("%lld
",ans);
return 0;
}