总结&吐槽
难得的把吐槽放到了最前面.这场比赛用的是一场网络赛,本来是要算校内训练积分的.比赛开始五分钟,我还处于刚刚读完两道题的状态,一看榜,北师大12题位居第一,所有题目的总过题人数已经破百了.后来才知道用了区域赛的原题,于是网络赛变成了手速(网速)赛.最后祝贺北师大的队伍191罚时13题AK位居榜首.
言归正传,一开始我去写C,结果大小写打错没看出来连WA两发.之后队友表示D题有结论让我直接莽,结果又是连WA4发...本来想打的正经一些,至此开始往欢乐赛的方向发展.队友自闭推式子,我去开H.之后一段时间找到了手感,切题很顺利,而且做题速度居然相当靠前(不看罚时).E题发现是一个B-Tree,写了一半写自闭了,交给了队友.这时教练终于忍不住解除了我们的限制,于是欢快地拿下来I和L.最后9题收尾2333.
至于网络赛用原题导致名额无法正常分配的问题,目前还没有出来解决办法.听说又爆出来了银川理工学院的一些黑料,那就静等吃瓜.最后贴张图以示尊敬.
比赛地址
可能过几天会失效
[A]Maximum Element In A Stack
题意
维护一个堆栈,要求支持Push和Pop操作,每次操作结束后输出最大值.
题解
签到题
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int n, m, a, b, c, p, q, last_pl[5000005], now_pl;
unsigned int st[5000005], tot, nowmax;
unsigned long long int ans = 0;
unsigned int SA, SB, SC;
unsigned long long int i;
unsigned int rng61() {
SA ^= SA << 16;
SA ^= SA >> 5;
SA ^= SA << 1;
unsigned int t = SA; SA = SB;
SB = SC;
SC ^= t ^ SA;
return SC;
}
void PUSH(unsigned int a) {
st[++tot] = a;
if (a > nowmax) {
nowmax = a;
last_pl[tot] = now_pl;
now_pl = tot;
}
ans ^= (i * nowmax);
}
void POP() {
if (tot == 0) {
return ;
}
if (now_pl == tot) {
now_pl = last_pl[tot];
nowmax = st[now_pl];
tot--;
} else tot--;
ans ^= (i * nowmax);
}
void gen() {
scanf("%d%d%d%d%u%u%u", &n, &p, &q, &m, &SA, &SB, &SC);
for (i = 1; i <= n; i++) {
if (rng61()%(p+q) < p) PUSH(rng61()%m+1);
else POP();
}
}
int main(){
int T; cin >> T;
for (int t = 1; t <= T; t++) {
memset(st, 0, sizeof(st));
tot = 0;
ans = 0;
nowmax = now_pl = 0;
gen();
printf("Case #%d: %llu\n", t, ans);
}
return 0;
}
[B]Rolling The Polygon
题意
给出一个凸n边形,按逆时针方向给出所有点的坐标.另外在多边形内部存在着给出的一点Q.一开始第一个点和第二个点之间的边平行放在x轴上,之后让这个多边形进行顺时针旋转,求旋转一周之后,点Q的运动轨迹的长度.
题解
Q的轨迹是一段段圆弧,每次计算出旋转的角度和半径,算出对应的弧长即可.
代码
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
constexpr int MN(100);
constexpr double EPS = 1e-6, INF = 1e22, PI = 3.141592653589793238462643383279502884197169399375105820974944592, RAD = 180 / PI;
struct Po
{
double x, y;
double operator |(const Po & o) const
{
return sqrt((x-o.x) * (x-o.x) + (y-o.y) * (y-o.y));
}
} p[MN], C;
int main()
{
int T;
scanf("%d", &T);
for (int CAS=1; CAS<=T; ++CAS)
{
int n;
scanf("%d", &n);
double sum = 0;
for (int i=1; i<=n; ++i)
scanf("%lf %lf", &p[i].x, &p[i].y);
scanf("%lf %lf", &C.x, &C.y);
for (int i=1; i<=n; ++i)
p[n+i] = p[i];
for (int i=1; i<=n; ++i)
{
double a = p[i] | p[i+1];
double b = p[i+1] | p[i+2];
double c = p[i+2] | p[i];
double r = C | p[i+1];
sum += ((PI - acos((a*a + b*b - c*c) / (2 * b*a))) * r);
}
printf("Case #%d: %.3lf\n", CAS, sum);
}
#ifdef _KEVIN
system("pause");
#endif
return 0;
}
[C]Caesar Cipher
题意
给出三个字符串.第二个字符串是第一个字符串经过凯撒密码的加密规则得到的.第三个字符串也是通过相同规则得到的.求对应的原串.
题解
签到题
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#define N 10000
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;
int T,j,i,x,n,t,m,f;
char a[N],b[N],c[N];
inline int Abs(int x){return (x<0)?-x:x;}
inline void Swap(int &a,int &b){a^=b^=a^=b;}
inline int Min(int a,int b){return (a<b)?a:b;}
inline int Max(int a,int b){return (a>b)?a:b;}
inline int read(){
int p=0; char c=getchar();
while (c<48||c>57) c=getchar();
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p;
}
int main(){
scanf("%d",&T);
for (j=1;j<=T;j++){
scanf("%d%d",&n,&m);
scanf("%s",&a);
scanf("%s",&b);
scanf("%s",&c);
t=(int)(b[0]-a[0]);
if (t<0) t+=26;
printf("Case #%d: ",j);
for (i=0;i<m;i++){
x=c[i]-t;
if (x<65) x=int('Z')+x-65+1;
printf("%c",(char)x);
}
cout<<endl;
}
return 0;
}
[D]Take Your Seat
题意
有n个人要坐飞机.编号从1~n.上飞机的顺序也是编号的顺序.第i个人的票上的座位是i位置.第1个人的票丢掉了,所以他会随机挑选一个座位坐下.当后面的某个人发现自己的座位被占掉了之后,他也会随机选一个座位;否则他将坐到自己票上的位置上.在飞机返回的时候,第1个人的票又丢了.此时有m个人,规则和之前一样,只是上飞机的顺序变成了随机的.求两次登机时,最后一个入座的人,恰好坐到自己票上位置的概率.
题解
设第一,二问中的答案为
f_n,g_n
第一问中,当第一个人坐到1号位时,后面所有人都能坐对;坐到第n号位时,最后一个人肯定不能坐对.当坐到第k位时,前k-1能坐对,k相当于变成了一开始的1.后面的n-k+1个人相当于随机选位置,于是产生了递推关系.则有
f_1=1,f_2=\frac{1}{2},f_n=\frac{\sum_{i=1}^{n-1}f_i}{n}
第二问相当于随机1的登机时间.当1是第k个登机的,则前面k-1个人能坐对.后面的n-k+1个人随机选位置.公式如下:
g_n=\frac{\sum_{i=1}^{n}f_i}{n}
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
double n, m;
int main(){
int T; cin >> T;
for (int t = 1; t <= T; t++) {
cin >> n >> m;
if (n == 1) printf("Case #%d: 1.000000 %.6lf\n", t, 0.5+(0.5/m));
else printf("Case #%d: 0.500000 %.6lf\n", t, 0.5+(0.5/m));
}
return 0;
}
[E]2-3-4 Tree
题意
给出n个数,按顺序插入到最小度数为2的B-Tree中.然后输出先序遍历的结果.
题解
关于B-Tree的理论见《算法导论》第三版 P277-P289
直接模拟建树过程即可.
本来数据结构是归我的,但这实在是太难写了于是交给了擅长指针的队友解决
代码
/*
* If we give,
* all we've got,
* we will make it through.
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <cctype>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <climits>
#define GC getchar()
#define _SN(x) {char _c=GC,_v=1;for(x=0;_c<48||_c>57;_c=GC)if(_c==45)_v=-1;for(;_c>=48&&_c<=57;x=(x<<1)+(x<<3)+_c-48,_c=GC);if(_v==-1)x=-x;}
#define _SAN(a,n) {auto _i=0,_n=n;for(;_i<_n;++_i)_SN(a[_i])}
#define _SA(a,l,r) {auto _i=l,_r=r;for(;_i<_r;++_i)_SN(a[_i])}
#define _gS(_1, _2, _3, _sc, ...) _sc
#define sc(...) _gS(__VA_ARGS__,_SA,_SAN,_SN, ...)(__VA_ARGS__)
#define _G1(_1) int _1;sc(_1)
#define _G2(_1,_2) int _1,_2;sc(_1)sc(_2)
#define _G3(_1,_2,_3) int _1,_2,_3;sc(_1)sc(_2)sc(_3)
#define _gG(_1,_2,_3,_get, ...) _get
#define get(...) _gG(__VA_ARGS__,_G3,_G2,_G1, ...)(__VA_ARGS__)
#define _F0N(i,n) for(auto i=0;i<(n);++i)
#define _FLR(i,l,r) for(auto i=(l);i<(r);++i)
#define _gF(_1, _2, _3, _F, ...) _F
#define F(...) _gF(__VA_ARGS__,_FLR,_F0N, ...)(__VA_ARGS__)
#define _FD0(i,n) for(auto i=0;i<=(n);++i)
#define _FDL(i,l,r) for(auto i=(l);i<=(r);++i)
#define _gFD(_1, _2, _3, _FD, ...) _FD
#define FD(...) _gFD(__VA_ARGS__,_FDL,_FD0, ...)(__VA_ARGS__)
#define FED(src) for(const auto *p=head[src]; p; p=p->next)
#define FRC(R,C) for(int r=0;r<R;++r)for(int c=0;c<C;++c)
#define OPER1(T,x1,b1) inline bool operator<(const T&_o)const{return x1 b1 _o.x1;}
#define OPER2(T,x1,b1,x2,b2) inline bool operator<(const T&_o)const{return x1 b1 _o.x1||x1==_o.x1&&x2 b2 _o.x2;}
#define OPER3(T,x1,b1,x2,b2,x3,b3) inline bool operator<(const T&_o)const{return x1 b1 _o.x1||x1==_o.x1&&(x2 b2 _o.x2||x2==_o.x2&&x3 b3 _o.x3);}
#define IL inline
#define LL long long
#define ULL unsigned LL
#define PC putchar
template<class T>
void UPRT(const T _){if(_>=10)UPRT(_/10);PC(_%10+48);}
#define UPL(_) UPRT(_),PC(10)
#define UPD(_) UPRT(_),PC(32)
template<class T>
void PRT(const T _){if(_<0){PC(45),UPRT<ULL>(-(ULL)_);return;}if(_>=10)PRT(_/10);PC(_%10+48);}
#define PL(_) PRT(_),PC(10)
#define PD(_) PRT(_),PC(32)
#define CON constexpr
#define T_CASE int T;sc(T)for(int CASE=1;CASE<=T;++CASE)
#define Tjj int T;sc(T)while(T--)
#define qjj int q;sc(q)while(q--)
#define cincout std::cin.tie(nullptr),std::cout.tie(nullptr),std::ios::sync_with_stdio(false)
#define EPS 1e-8
#define PI 3.141592653589793238
#define MAX_INT 2147483647
#define MIN_INT -2147483648
#define MAX_LL 9223372036854775807LL
#define MIN_LL -9223372036854775808LL
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3fLL
#define priority_queue priority_queue
#define unordered_ unordered_
using std::cin;
using std::cout;
using std::string;
using std::priority_queue;
using std::pair;
using std::vector;
using std::deque;
using std::set;
using std::map;
using std::unordered_set;
using std::unordered_map;
using std::bitset;
using std::sort;
#define MPFD(k) auto it=mp.find(k)
#define MIN(a, b) ((a)<(b)?(a):(b))
#define MIN3(a, b, c) (MIN(a, MIN(b, c)))
#define MAX(a, b) ((a)>(b)?(a):(b))
#define MAX3(a, b, c) (MAX(a, MAX(b, c)))
#define MAXER(a, b) ({if(a<b)a=b;a;})
#define MINER(a, b) ({if(a>b)a=b;a;})
#define MAXA(bg, ed) ({auto __mv=(bg);for(auto __it=__mv+1,__ed=(ed);__it!=__ed;++__it)if(*__it>*__mv)__mv=__it;__mv;})
#define MINA(bg, ed) ({auto __mv=(bg);for(auto __it=__mv+1,__ed=(ed);__it!=__ed;++__it)if(*__it<*__mv)__mv=__it;__mv;})
#define FIND(bg, ed, k) ({auto __pk=(bg);__pk=nullptr;for(auto __it=(bg),__ed=(ed);__it!=__ed;++__it)if(*__it==k){__pk=__it;break;}__pk;})
#define ABS(a) ((a)>0?(a):-(a))
#define FABS(a) ((a)>0?(a):-(a))
#define log2n(x) (log(x)/0.69314718055995)
#define MHD(p1, p2) ((p1.x>p2.x?p1.x-p2.x:p2.x-p1.x)+(p1.y>p2.y?p1.y-p2.y:p2.y-p1.y))
#define DIST(p1, p2) sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y))
#define PB emplace_back
#define EB emplace_back
#define EBK else break
#define ALL(X) (X).begin(),(X).end()
#define SORT(X) std::sort(ALL(X))
#define SORTD(X) std::sort(ALL(X),std::greater<decltype((X)[0])>())
#define SW(a,b) ({auto _t=a;a=b;b=_t;})
#define mem0(a) memset(a,0,sizeof(a))
#define memf1(a) memset(a,-1,sizeof(a))
#define meminf(a) memset(a,0x3f,sizeof(a))
#define GCD(a,b) ({auto __tp=a,__a=a,__b=b;while(__b){__tp=__a%__b;__a=__b;__b=__tp;}__a;})
CON int MN(1e5);
CON int INVALID_VAL(1e9);
enum VAL_IDX
{
L_VAL, M_VAL, R_VAL, VAL_N
};
enum PTR_IDX
{
P_LL, P_ML, P_MR, P_RR, PTR_N
};
template <typename vint>
class Tree
{
private:
struct Node
{
int vn;
vint val[VAL_N];
Node *son[PTR_N], *fa;
bool empty(void) const {return !vn;}
bool full(void) const {return vn == VAL_N;}
void ins_v(vint v)
{
val[vn++] = v;
if (val[0] > val[1])
SW(val[0], val[1]);
if (val[0] > val[2])
SW(val[0], val[2]);
if (val[1] > val[2])
SW(val[1], val[2]);
}
int get_son_pos(vint v) const
{
int pos;
for (pos=0; pos<vn; ++pos)
if (val[pos] > v)
break;
return pos;
}
} _pool[MN], *pool;
Node _NIL, *NIL, *root;
bool is_leaf(const Node *p) const {return p->son[0]==NIL and p->son[1]==NIL and p->son[2]==NIL and p->son[3]==NIL;}
Node *new_node(const vint v, Node *fa)
{
++pool;
pool->vn = 1;
pool->val[0] = v;
pool->val[1] = pool->val[2] = INVALID_VAL;
for (int i=0; i<PTR_N; ++i)
pool->son[i] = NIL;
pool->fa = fa;
return pool;
}
void ins_first(vint v)
{
root = new_node(v, NIL);
}
Node *push_up(Node *p)
{
Node *fa = p->fa, *left, *right;
if (fa == NIL)
{
fa = root = new_node(p->val[M_VAL], NIL);
left = new_node(p->val[L_VAL], fa);
right = new_node(p->val[R_VAL], fa);
fa->son[0] = left, fa->son[1] = right;
left->son[0] = p->son[0], left->son[1] = p->son[1];
p->son[0]->fa = p->son[1]->fa = left;
right->son[0] = p->son[2], right->son[1] = p->son[3];
p->son[2]->fa = p->son[3]->fa = right;
}
else
{
int pos = fa->get_son_pos(p->val[M_VAL]);
fa->ins_v(p->val[M_VAL]);
left = new_node(p->val[L_VAL], fa);
right = new_node(p->val[R_VAL], fa);
left->son[0] = p->son[0], left->son[1] = p->son[1];
p->son[0]->fa = p->son[1]->fa = left;
right->son[0] = p->son[2], right->son[1] = p->son[3];
p->son[2]->fa = p->son[3]->fa = right;
for (int i=P_RR; i>pos+1; --i)
fa->son[i] = fa->son[i-1];
fa->son[pos] = left, fa->son[pos+1] = right;
}
return fa;
}
void dfs(Node *p) const
{
if (p == NIL)
return;
for (int i=0; i<p->vn; ++i)
printf("%d ", p->val[i]);
puts("");
for (int i=0; i<p->vn+1; ++i)
dfs(p->son[i]);
}
public:
Tree(void) :
pool(_pool),
NIL(&_NIL),
root(NIL)
{
NIL->vn = 0;
for (int i=0; i<VAL_N; ++i)
NIL->val[i] = INVALID_VAL;
for (int i=0; i<PTR_N; ++i)
NIL->son[i] = NIL;
NIL->fa = NIL;
}
void clear()
{
pool = _pool;
root = NIL;
}
void insert(vint v)
{
if (root == NIL)
ins_first(v);
else
{
Node *p = root;
while (not is_leaf(p))
{
if (p->full())
p = push_up(p);
p = p->son[p->get_son_pos(v)];
}
if (p->vn == VAL_N)
{
p = push_up(p);
p = p->son[p->get_son_pos(v)];
}
p->ins_v(v);
}
}
void dfs(void) const
{
dfs(this->root);
}
};
Tree<int> t;
int main()
{
int T;
scanf("%d", &T);
for (int CAS=1; CAS<=T; ++CAS)
{
t.clear();
int n;
scanf("%d", &n);
while (n--)
{
int x;
scanf("%d", &x);
t.insert(x);
}
printf("Case #%d:\n", CAS);
t.dfs();
}
#ifdef _KEVIN
system("pause");
#endif
return 0;
}
[F]Moving On
题意
给出n个点,每个点有一个不安全系数.现在有q个询问,每次询问u到v之间的不经过不安全系数超过w的最短路的长度.
题解
签到题
代码
#include <cstdio>
#include <cstring>
#include <algorithm>
constexpr int MN(222);
constexpr int INF(0x3f3f3f3f);
int G[MN][MN][MN];
struct Node
{
int id, danger;
Node(void) { }
Node(int idd, int dangerr) :
id(idd), danger(dangerr)
{
}
bool operator <(const Node &o) const
{
return danger < o.danger;
}
} a[MN];
#define MIN(a, b) ((a)<(b)?(a):(b))
int main()
{
int T;
scanf("%d", &T);
for (int CAS=1; CAS<=T; ++CAS)
{
memset(G, INF, sizeof(G));
int V, Q;
scanf("%d%d", &V, &Q);
for (int i = 1; i <= V; i++)
{
a[i].id = i;
scanf("%d", &a[i].danger);
}
std::sort(a + 1, a + V + 1);
for (int i = 1; i <= V; i++)
for (int j = 1; j <= V; j++)
scanf("%d", &G[0][i][j]);
for (int k = 1; k <= V; k++)
for (int i = 1; i <= V; i++)
for (int j = 1; j <= V; j++)
G[k][i][j] = MIN(G[k - 1][i][j], G[k - 1][i][a[k].id] + G[k - 1][a[k].id][j]);
printf("Case #%d:\n", CAS);
while (Q--)
{
int u, v, w;
scanf("%d %d %d", &u, &v, &w);
printf("%d\n", G[std::upper_bound(a+1, a+V+1, Node(0, w))-(a+1)][u][v]);
}
}
#ifdef _KEVIN
system("pause");
#endif
return 0;
}
[H]Fight Against Monsters
题意
有n个怪兽,每个怪兽有一个生命值和攻击力.然后玩家需要和怪兽进行回合制战斗,每一回合是怪兽先手,会对玩家造成等同于现在存活怪兽的攻击力总和的伤害;之后由玩家进攻,每次只能攻击一个怪兽.对一个怪兽造成的伤害为k,k是对这个怪兽的累计攻击次数.所以对一个怪兽造成的伤害将会是1,2,3,4...求消灭掉所有怪兽时,玩家承受的伤害的最小值是多少.
题解
和NOIP2013的国王游戏非常像.
首先有个显然的结论,那就是攻击怪兽的时候,每次选定一个怪兽,直到把它打死之后再换一个怪兽攻击.怪兽的血量可以转化为一个攻击次数t,设怪兽的攻击力为a.下面考虑如何安排攻击顺序.
如果假设安排i号怪兽在j号怪兽前面比j在i前面更优(忽略中间的其他怪兽),则有
t_ia_i+t_ia_j+t_ja_j \leq t_ja_j+t_ja_i+t_ia_i
化简得
t_ia_j \leq t_ja_i
所以按这个顺序排序,然后直接计算答案即可.
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#define N 100010
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;
int i,j,n,T;
LL Ans;
int s[1010],a[N],h[N];
struct Data{
LL x,y;
}t[N];
inline bool cmp(Data a,Data b){return a.x*b.y<b.x*a.y;}
inline int Abs(int x){return (x<0)?-x:x;}
inline void Swap(int &a,int &b){a^=b^=a^=b;}
inline int Min(int a,int b){return (a<b)?a:b;}
inline int Max(int a,int b){return (a>b)?a:b;}
inline int read(){
int p=0; char c=getchar();
while (c<48||c>57) c=getchar();
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p;
}
inline void Ready(){
int i=0;
for (i=1;i<=1000;i++) s[i]=i*(i+1)/2;
}
inline int Find(int x){
int low=1,high=1000,mid=0,ans=0;
while (low<=high){
mid=(low+high)>>1;
if (s[mid]>=x) ans=mid,high=mid-1;
else low=mid+1;
}
return ans;
}
inline void Work(){
int i=0;
memset(t,0,sizeof(t));
for (i=1;i<=n;i++){
t[i].x=Find(h[i]); t[i].y=a[i];
}
sort(t+1,t+1+n,cmp);
LL tot=0;
Ans=0;
for (i=1;i<=n;i++){
Ans+=tot*t[i].y;
Ans+=t[i].x*t[i].y;
tot+=t[i].x;
}
}
int main(){
Ready();
scanf("%d",&T);
for (j=1;j<=T;j++){
scanf("%d",&n);
for (i=1;i<=n;i++) scanf("%d%d",&h[i],&a[i]);
Work();
printf("Case #%d: ",j);
cout<<Ans<<endl;
}
return 0;
}
[I]Bubble Sort
题意
给出一段冒泡排序的伪代码和交换次数的定义.定义一个长度为n的序列是几乎有序的当且仅当其LIS的长度不小于n-1.现在需要找出符合题意的1~n的排列总数,要求这个拍立恩在经过至多k次交换后,可以变成几乎有序的.
题解
有待补充
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#define N 1010
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;
LL n,k,i,T,j,MOD,Ans;
LL mi[N],jc[N];
inline int Abs(int x){return (x<0)?-x:x;}
inline void Swap(int &a,int &b){a^=b^=a^=b;}
inline int Min(int a,int b){return (a<b)?a:b;}
inline int Max(int a,int b){return (a>b)?a:b;}
inline LL read(){
LL p=0; char c=getchar();
while (c<48||c>57) c=getchar();
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p;
}
inline void Ready(){
LL i=0;
memset(mi,0,sizeof(mi));
memset(jc,0,sizeof(0));
mi[0]=1; jc[0]=1;
for (i=1;i<=n;i++) mi[i]=(mi[i-1]*(LL)(k+1))%MOD;
for (i=1;i<=n;i++) jc[i]=(jc[i-1]*(LL)i)%MOD;
return;
}
inline void Work(){
LL i=0,x=0,cnt=0;
Ans=mi[n-k];
for (i=3;i<=n-k;i++){
x=(mi[n-k-i+1]*(n-i-k+1)%MOD)%MOD;
cnt=(cnt+x)%MOD;
}
for (i=2;i<=n-k;i++){
x=(mi[n-k-1]*(n-i-k+1)%MOD)%MOD;
cnt=(cnt+x)%MOD;
}
Ans=(Ans+cnt)%MOD;
Ans=(Ans*jc[k])%MOD;
return;
}
int main(){
T=read();
for (j=1;j<=T;j++){
printf("Case #%d: ",j);
n=read(); k=read(); MOD=read();
Ans=0;
if (k>=n){
Ans=1;
for (i=1;i<=n;i++) Ans=(Ans*(LL)i)%MOD;
printf("%lld\n",Ans);
continue;
}
Ready(); Work();
printf("%lld\n",Ans);
}
return 0;
}
[L]Continuous Intervals
题意
给出一个长度为n的序列.称一个其中[l,r]的子列是连续的,当且仅当把这段区间的所有数排序后,相邻两项的差至多为1.求有多少子列是连续的.
题解
设一个区间[l,r]内的最大值为max,最小值为min,数字种类数为cnt.当且仅当
max-min-cnt=-1
时,符合题意.
然后考虑用线段树维护以l为左端点的所有区间中max-min-cnt的最小值以及有多少区间符合题意.对于max和min,可以使用单调栈维护.对于cnt,可以考虑每个数的贡献.设a上次出现的位置是
last_a
这次出现的位置是i,则只需要对
[last_a+1,i]
区间进行加1操作即可.因为数据较为离散,然后拿一个map维护就好了.最后需要检查一下最小值是不是-1.具体细节见代码.
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#define N 100010
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;
int i,j,T,n,top,Top,w,ss;
int a[N];
LL Ans=0;
map <int,int> M;
struct Tree{
int l,r,d,lz,sum;
}t[N*4];
struct Data{
int x,y;
}d[N],x[N],ans;
inline int Abs(int x){return (x<0)?-x:x;}
inline void Swap(int &a,int &b){a^=b^=a^=b;}
inline int Min(int a,int b){return (a<b)?a:b;}
inline int Max(int a,int b){return (a>b)?a:b;}
inline int read(){
int p=0; char c=getchar();
while (c<48||c>57) c=getchar();
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p;
}
inline void Maketree(int x,int low,int high){
int mid=(low+high)>>1;
t[x].l=low; t[x].r=high;
if (low==high) {t[x].sum=1; return;}
Maketree(l(x),low,mid); Maketree(r(x),mid+1,high);
t[x].sum=t[l(x)].sum+t[r(x)].sum;
}
inline void Push(int x){
int p=t[x].lz;
if (p==0) return;
if (!t[x].l) return;
t[l(x)].d+=p; t[r(x)].d+=p;
t[l(x)].lz+=p; t[r(x)].lz+=p;
t[x].lz=0;
}
inline void Add(int x,int low,int high,int val){
int mid=(t[x].l+t[x].r)>>1;
//cout<<x<<" "<<low<<" "<<high<<endl;
if (low==t[x].l&&high==t[x].r){
t[x].d+=val; t[x].lz+=val;
return;
}
if (t[x].lz!=0) Push(x);
if (high<=mid) Add(l(x),low,high,val);
else if (low>mid) Add(r(x),low,high,val);
else Add(l(x),low,mid,val),Add(r(x),mid+1,high,val);
t[x].d=Min(t[l(x)].d,t[r(x)].d);
if (t[l(x)].d==t[r(x)].d) t[x].sum=t[l(x)].sum+t[r(x)].sum;
else if (t[l(x)].d<t[r(x)].d) t[x].sum=t[l(x)].sum;
else t[x].sum=t[r(x)].sum;
}
inline Data Query(int x,int low,int high){
int mid=(t[x].l+t[x].r)>>1;
Data X,y;
if (t[x].l==low&&t[x].r==high) return (Data){t[x].d,t[x].sum};
if (high<=mid) return Query(l(x),low,high);
else if (low>mid) return Query(r(x),low,high);
else {
X=Query(l(x),low,mid);
y=Query(r(x),mid+1,high);
if (X.x==y.x) return (Data){y.x,X.y+y.y};
if (X.x<y.x) return X; else return y;
}
}
int main(){
scanf("%d",&T);
for (j=1;j<=T;j++){
scanf("%d",&n);
for (i=1;i<=n;i++) scanf("%d",&a[i]);
printf("Case #%d: ",j);
memset(t,0,sizeof(t)); memset(d,0,sizeof(d)); memset(x,0,sizeof(x));
top=Top=0; Ans=0; M.clear();
Maketree(1,1,n);
for (i=1;i<=n;i++){
while (top){
if (a[i]<=d[top].x) break;
w=d[top].y;
Add(1,d[top-1].y+1,w,a[i]-d[top].x);
top--;
}
d[++top]=(Data){a[i],i};
while (Top){
if (a[i]>=x[Top].x) break;
w=x[Top].y;
Add(1,x[Top-1].y+1,w,x[Top].x-a[i]);
Top--;
}
x[++Top]=(Data){a[i],i};
Add(1,M[a[i]]+1,i,-1); M[a[i]]=i;
ans=Query(1,1,i);
if (ans.x==-1) Ans+=ans.y;
}
printf("%lld\n",Ans);
}
return 0;
}
声明:
本文采用
BY-NC-SA
协议进行授权，如无注明均为原创，转载请注明转自
Marvolo
本文地址: ACM暑期集训第十二场(Unrated)
本文地址: ACM暑期集训第十二场(Unrated)
