为了拓宽自己的英雄池，还是要写一下。
分数 & 排名：
理想：
会牵挂的叫亲人，回不去的是故乡。
现实：
神虎一跃，威震天地！
A. 李时珍的皮肤衣
今天输了，明天也要卷土重来。
赛后加点卡赛时是不理解的。为啥这次就加点，上次数据范围错了都不把数据范围错的删了给我重测。
自己手动模拟一下小的数，易得答案为 \(2^{n-1}+1\pmod{n}\)。
由于 \(n\) 是 \(10^{10}\)，所以快速幂过程中有概率炸 long long，因此开 __int128 即可。
梦想什么的，不重要了。那里还有等着俺的兄弟。
#include <bits/stdc++.h>
#define int __int128
using namespace std;
int n;
int ksm(int a,int b){
int res = 1;
while(b){
if(b & 1) res = res * a % n;
a = a * a % n;b >>= 1;
}
return res;
}
signed main(){
freopen("lsz.in","r",stdin);
freopen("lsz.out","w",stdout);
scanf("%lld",&n);
printf("%lld",(ksm(2,n - 1) + 1) % n);
return 0;
}
B. 马大嘴的废话
眼泪，不知不觉留下来。琴里燃烧着的，是长城的篝火。
暴力枚举每个字符串里面的子串，\(O(1)\) 查询。
打个赌，阴险的敌人，永远不敢来场堂堂正正的对决。
#include <bits/stdc++.h>
using namespace std;
int n,Q;string s;
unordered_map < string , int > sum,p;
void Input(){
scanf("%d",&n);
for(int i = 1;i <= n;i ++){
cin >> s;p.clear();
for(int j = 0;j < s.size();j ++){
string t = "";
for(int k = j;k < s.size();k ++){
string o;o = s[k];t = t + o;
if(!p[t]) sum[t] ++,p[t] = 1;
}
}
}
}
void work(){
scanf("%d",&Q);while(Q --){
cin >> s;printf("%d\n",sum[s]);
}
}
signed main(){
freopen("mdz.in","r",stdin);
freopen("mdz.out","w",stdout);
Input();work();return 0;
}
C. SSY的队列
历史对我紧追不舍，但我速度更快。
不会。状压没学过，hash 没学过，改牛魔。
D. 清理牛棚
以无限为有限，以无法为有法。
看到洛谷题解的思路好巧。输入按照有向边建边，然后每个点向前一个点建一个边权为 \(0\) 的边，然后跑最短路就行了。
还有一个思路就是数据结构优化 \(DP\)，由于有上面很显然简单的做法，所以没改。
我不怕练过一万种腿法的对手，只怕把一种腿法练一万次的对手。
#include <bits/stdc++.h>
#define N 100005
#define int long long
using namespace std;
int n,M,E,dis[N],vis[N];
struct Edge{int next,to,dis;}edge[N << 1];
int head[N],cnt;
void add(int from,int to,int dis){
edge[++cnt] = (Edge){head[from],to,dis};
head[from] = cnt;
}
struct Node{
int pos,dis;
bool operator <(const Node x) const{
return x.dis < dis;
}
};
priority_queue < Node > q;
int dij(){
for(int i = M;i <= E + 1;i ++) dis[i] = 1e15;
dis[M] = 0;q.push((Node){M,0});
while(!q.empty()){
Node tmp = q.top();q.pop();
int x = tmp.pos;
if(vis[x]) continue;
for(int i = head[x];i;i = edge[i].next){
int y = edge[i].to;
if(dis[y] > dis[x] + edge[i].dis){
dis[y] = dis[x] + edge[i].dis;
if(!vis[y]) q.push((Node){y,dis[y]});
}
}
}
return dis[E + 1] == 1e15 ? -1 : dis[E + 1];
}
signed main(){
freopen("clean.in","r",stdin);
freopen("clean.out","w",stdout);
scanf("%lld%lld%lld",&n,&M,&E);
for(int i = 1,u,v,w;i <= n;i ++){
scanf("%lld%lld%lld",&u,&v,&w);
add(u,v + 1,w);
}
for(int i = M + 1;i <= E;i ++) add(i,i - 1,0);
printf("%lld\n",dij());
return 0;
}
E. 历史研究
点击查看代码
跟蒲公英类似的，包括预处理什么东西，怎么预处理也类似，就不说了，参考蒲公英就行。
当然也是回滚莫队板子，不会。
开战前没必要打赌，结果无非我赢你输。
#include <bits/stdc++.h>
#define N 100005
#define M 320
#define int long long
using namespace std;
struct T{int l,r;}t[M];
int n,m,Q,len,a[N],b[N],block[N],p[M][M],f[M][N],tmp[N];
void Input(){
scanf("%lld%lld",&n,&Q);len = sqrt(n);int k = n / len;
for(int i = 1;i <= k;i ++) t[i].l = (i - 1) * len + 1,t[i].r = i * len;t[k].r = n;
for(int i = 1;i <= k;i ++) for(int j = t[i].l;j <= t[i].r;j ++) block[j] = i;
for(int i = 1;i <= n;i ++) scanf("%lld",&a[i]),b[i] = a[i];
sort(b + 1,b + n + 1);m = unique(b + 1,b + n + 1) - b - 1;
for(int i = 1;i <= n;i ++) a[i] = lower_bound(b + 1,b + m + 1,a[i]) - b;
for(int i = 1;i <= k;i ++){
for(int j = t[i].l;j <= t[i].r;j ++) f[i][a[j]] += b[a[j]];
for(int j = 1;j <= m;j ++) f[i][j] += f[i - 1][j];
}
for(int i = 1;i <= k;i ++){
int MAX = 0;
for(int j = 1;j <= k;j ++){
for(int l = t[j].l;l <= t[j].r;l ++){
if(f[j][a[l]] - f[i - 1][a[l]] >= f[j][MAX] - f[i - 1][MAX]) MAX = a[l];
}
p[i][j] = f[j][MAX] - f[i - 1][MAX];
}
}
}
void work(){
int l,r;while(Q --){
scanf("%lld%lld",&l,&r);
int bl = block[l],br = block[r],MAX = 0;
if(br - bl <= 1){
for(int i = l;i <= r;i ++) tmp[a[i]] += b[a[i]],MAX = max(MAX,tmp[a[i]]);
for(int i = l;i <= r;i ++) tmp[a[i]] = 0;printf("%lld\n",MAX);continue;
}
for(int i = l;i <= t[bl].r;i ++) tmp[a[i]] += b[a[i]];
for(int i = t[br].l;i <= r;i ++) tmp[a[i]] += b[a[i]];
for(int i = l;i <= t[bl].r;i ++) if(tmp[a[i]] + f[br - 1][a[i]] - f[bl][a[i]] >= tmp[MAX] + f[br - 1][MAX] - f[bl][MAX]) MAX = a[i];
for(int i = t[br].l;i <= r;i ++) if(tmp[a[i]] + f[br - 1][a[i]] - f[bl][a[i]] >= tmp[MAX] + f[br - 1][MAX] - f[bl][MAX]) MAX = a[i];
printf("%lld\n",max(tmp[MAX] + f[br - 1][MAX] - f[bl][MAX],p[bl + 1][br - 1]));
for(int i = l;i <= t[bl].r;i ++) tmp[a[i]] = 0;
for(int i = t[br].l;i <= r;i ++) tmp[a[i]] = 0;
}
}
signed main(){
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
Input();work();return 0;
}