2017zstu新生赛

1.b^3 - a^3 = c（zy）

zy说要卡nlogn的，然而他实际给的组数只有100组，然后因为在windows下随机的，所以给出的 c <= 100000。然后只要胆子大。。。。

通过打表发现，x^3-(x-1)^3 <= 1e9, x的最大值是18258

然后我们用一个数组去记录 2^3-1^3, 3^3-2^3, 4^3-3^3, ...., 18258^3-18257^3

对于c, 用尺取去判断就好了

#include
using namespace std;
typedef long long ll;
const int UP = 18258 + 10;
vector ss;
int c;int main () {for (ll i=2; ii) {ss.emplace_back(i*i*i-(i-1)*(i-1)*(i-1));}freopen("1.in","r",stdin);freopen("11.out","w",stdout);while (~ scanf("%d", &c)) {ll sum = 0;deque<int> q;bool flag = false;for (int i=0; ii) {q.push_back(i);sum += ss[i];while (!q.empty() && sum>c) {sum -= ss[q.front()];q.pop_front();}if (sum==c) {flag = true;printf ("%d %d\n", q.front()+1, q.back()+2);break;}}if (!flag) puts("-1");}return 0;
}

2.cs的禁断魔法（zy）

主席树 + 二分，然后感觉是所有题里写起来最费劲的

deep是点在树上的深度，maxdeep(i) : 表示在i这棵子树里，会出现的最大deep

把所有点按照(deep, val)去sort，然后按照deep从小到大去建主席树。

建主席树就是按照dfs序插入到线段树里，然后区间维护最小值。

然后对于每次询问 x c, 就二分深度，然后用主席树check就好了

总体复杂度：O(nlogn + Qloglog)

#include
using namespace std;
const int inf = 0x3f3f3f3f;
const int M = 1e5+10;
const int logn = 22;
const int nill = 0;
typedef pair<int,int> pii;
int deep[M], maxndeep[M];
pii a[M];
int val[M];
vector<int> g[M];
int tin[M], tout[M], tim;
int n, Q;void dfs (int u) {tin[u] = ++tim;maxndeep[u] = deep[u];for (int i=0; ii) {int v = g[u][i];deep[v] = deep[u]+1;a[v].first = a[u].first+1;a[v].second = v;dfs(v);maxndeep[u] = max(maxndeep[u], maxndeep[v]);}tout[u] = tim;
}int rt[M], ls[M*logn], rs[M*logn], T[M*logn];struct Segtree {int sz;int alloc(int u) {T[sz] = T[u], ls[sz] = ls[u], rs[sz] = rs[u], T[sz] = T[u];return sz ++;}void init() {rt[nill] = ls[nill] = rs[nill] = 0, T[nill] = inf;sz = 1;}void ins(int &o,int u,int l,int r,int x,int val) {o = alloc(u);T[o] = min(T[o], val);if (l==r) return;int mid = l+r>>1;if (x<=mid) ins(ls[o],ls[u],l,mid,x,val);else ins(rs[o],rs[u],mid+1,r,x,val);}int ask(int o,int l,int r,int pl,int pr) {if (pl<=l&&r<=pr) return T[o];int mid = l+r>>1;if (pl<=mid && pr>mid) return min(ask(ls[o],l,mid,pl,pr), ask(rs[o],mid+1,r,pl,pr));if (pl<=mid) return ask(ls[o],l,mid,pl,pr);return ask(rs[o],mid+1,r,pl,pr);}
}sgt;int solve(int x,int c) {int l = deep[x], r = maxndeep[x], ret = -1;//printf ("maxndeep(%d)=%d\n", x, maxndeep[x]);//printf ("pl=%d,pr=%d\n", tin[x], tout[x]);//printf ("%d,%d:l=%d,r=%d\n", x,c,l,r);while (l <= r) {int mid = l+r>>1;//printf ("ask(%d)=%d\n", mid, sgt.ask(rt[mid],1,n,tin[x],tout[x]));if (sgt.ask(rt[mid],1,n,tin[x],tout[x]) > c) {ret = mid, l = mid+1;} else r = mid-1;}//printf ("ret=%d\n", ret);return ret==-1 ? 0 : ret - deep[x] + 1;
}int main () {//freopen("2.in", "r", stdin);//freopen("22.out","w",stdout);while (~scanf("%d%d", &n,&Q)) {for (int i=1; i<=n; ++i) {g[i].clear();scanf ("%d", val+i);}for (int i=2, u; i<=n; ++i) {scanf ("%d", &u);g[u].push_back(i);}a[1] = make_pair(1, 1);deep[1] = 1;tim = 0;dfs(1);sort(a+1, a+1+n);sgt.init();for (int i=1,j=1; i<=maxndeep[1]; ++i) {rt[i] = rt[i-1];while(j<=n && a[j].first == i) {sgt.ins(rt[i],rt[i],1,n,tin[a[j].second], val[a[j].second]);++j;}}//puts("------------------");int x, c;while (Q --) {scanf ("%d%d", &x,&c);printf ("%d\n", solve(x,c));}}return 0;
}

3.CS考四级（lyf）

 后缀自动机，本来想教下16级小朋友的，然后好像没有时间了，大概留下个坑，让他们自己填吧，hhhhh

首先把每个串按照 #s1#s2#s3#....sn差到sam里，（这里的#指标是特殊字符而已，我的模板里通过Inskey()函数来实现）

对于sam里的叶子节点可以通过len(i)数组和 #s1#s2#s3#....sn进行映射，找到对应的id

然后我们维护sam里的每个节点的 （min(id), max(id))即可，如果这两个值出现在同一个字符串s(i)里，那么对于当前这个节点来说，

它所有可以接受的串都是s(i)的特征串

因为题目要求每个串字典序最小的，所以再dfs处理下就好了

总体复杂度：O(segma(s(i))

//注意：因为 sam 在头部插入了一个 nill 字符（如果没有nill，right集会少
//所以对于 parent树 的叶子：
//如果 l(leaf) == l(fa(leaf)) + 1, 那么说明实际上从 fa(leaf) -> leaf这条边实际上是通过走 nill 字符通过的，
//及原串实际上是不会走到这个节点的。
//hdu6194
#include
using namespace std;
const int inf = 0x3f3f3f3f;
const int M = 2e5 + 10;
int n;
char s[M];
int col[M<<1];
string ans[M];struct SAM {static const int kN = M << 1;static const int chN = 26;int fa[kN];int go[kN][chN];int l[kN];int o;int rt;int lst;inline int newNode(int _l) {for (int i=0; ii) {go[o][i] = -1;}l[o] = _l;return o ++;}void Init() {o = 0;rt = lst = newNode(0);fa[rt] = -1;}inline void InsKey() {int p = lst, np = newNode(l[lst]+1); lst = np;fa[np] = rt;}inline void Ins(int c) {int p = lst, np = newNode(l[lst]+1); lst = np;//printf ("%c:%d\n", c+'a', np);while (~p && go[p][c] == -1) go[p][c] = np, p = fa[p];if (p==-1) fa[np] = rt;else {int q = go[p][c];if (l[p]+1 == l[q]) fa[np] = q;else {int nq = newNode(l[p]+1);//printf ("%c:%d\n", c+'a', nq);memcpy(go[nq], go[q], sizeof(go[q]));fa[nq] = fa[q];fa[q] = fa[np] = nq;while (~p && go[p][c] == q) go[p][c] = nq, p = fa[p];}}}//topoint ord[kN];int cnt[kN];int right[kN];int in[kN];void topo() {int maxVal = 0;memset (cnt, 0, sizeof(cnt[0])*o);for (int i=0; i cnt[l[i]];for (int i=1; i<=maxVal; ++i) cnt[i] += cnt[i-1];for (int i=0; i i;}int cc[kN][2];vector<char> st;void dfs(int o) {if (o!=rt) {//printf ("%d:(%d,%d), ", o, cc[o][0], cc[o][1]);//cout << st << endl;if (cc[o][0] == cc[o][1] && !cnt[cc[o][0]]) {cnt[cc[o][0]] = 1;for (int i=0; i0]] += st[i];//ans[cc[o][0]] = st;
            }}for (int i=0; i<26; ++i) if (go[o][i]!=-1){st.push_back('a'+i);dfs(go[o][i]);st.pop_back();}}void solve() {//for (int i=1; i
        topo();memset (cnt, 0, sizeof(cnt[0])*o);memset (in, 0, sizeof(in[0])*o);for (int i=1; iin[fa[i]];for (int i=1; ii) {if(!in[i]) {//printf ("%d:l=%d,col=%d\n", i, l[i], col[l[i]-1]);cc[i][0] = cc[i][1] = col[l[i]-1];} else {cc[i][0] = inf, cc[i][1] = -inf;}}for (int i=o-1; i>0; --i) {int f = fa[ord[i]];cc[f][0] = min(cc[f][0], cc[ord[i]][0]);cc[f][1] = max(cc[f][1], cc[ord[i]][1]);}st.clear();dfs(rt);}
} sam;int main () {//freopen("3.in", "r", stdin);//freopen("3.out", "w", stdout);while (~scanf("%d", &n)) {sam.Init();int len = 0;for (int i=0; ii) {ans[i].clear();sam.InsKey();col[len ++] = i;// ????scanf ("%s", s);for (int j=0; s[j]; ++j) {sam.Ins(s[j]-'a');col[len ++] = i;}}sam.solve();for (int i=0; ii) {if (ans[i].empty()) puts("-1");else cout << ans[i] << endl;}}return 0;
}
/*
2
aba
ab2
ab
ab2
bd
ad4
abd
bdc
ddd
abab
*/

4.这不珂学 (lyf)

莫队+莫比乌斯容斥

大概高年级所有人都会求 n 个数的互质对数吧？（不会的话，请先去学这个）。

然后你会发现算贡献的时候，其实就只和每个数的约数有关系，所以一个个算显然也是没有问题的。。。然后就没了

总体复杂度：O(n*sqrt(n)*60)，60是因为1e4以内的数约数数量的最大值是60

#include
using namespace std;
const int M = 1e5 + 10;
const int block = 150;
typedef long long ll;vector<int> yue[M];
vector<bool> isprime;
vector<int> mu;
void sieve () {isprime.assign(M, true);isprime[0] = isprime[1] = false;for (int i=2; iif (isprime[i]) {for (int j=i*i; ji) {isprime[j] = false;}}mu.assign(M, 1);for (int i=2; iif (isprime[i]) {if (ii) {for (int j=i*i; j0;}for (int j=i; j1;}for (int i=1; ii) {for (int j=i; ji) {yue[j].push_back(i);}}
}int n, m;
int a[M];
int ans[M];
int cnt[M];
int l, r;
int nowAns;struct Query {int l, r;int id;bool operator < (const Query &rhs) const {if (l/block == rhs.l/block) {return r < rhs.r;}return l < rhs.l;}
}qu[M];void Move(int x,int tp) {//printf ("a(%d)=%d, tp=%d\n", x, a[x], tp);if (tp==1) {for (int i=0; ii) {int &v = yue[a[x]][i];//printf ("cnt(%d)=%d\n",v , cnt[v]);nowAns += 1ll*mu[v]*cnt[v];++cnt[v];}} else {for (int i=0; ii) {int &v = yue[a[x]][i];--cnt[v];nowAns -= 1ll*mu[v]*cnt[v];}}//printf ("nowAns=%I64d\n", nowAns);
}void solve() {sort(qu, qu+m);l = r = nowAns = 0;for (int i = 0; i < m; ++i) {const Query &q = qu[i];while (l > q.l) Move(--l, 1);while (r < q.r) Move(++r, 1);while (l < q.l) Move(l++, -1);while (r > q.r) Move(r--, -1);ans[q.id] = nowAns;}
}int main () {sieve();//freopen("4.in", "r", stdin);//freopen("4.out", "w", stdout);while (~scanf ("%d%d", &n,&m)) {for (int i=1; i<=n; ++i) {scanf ("%d", a+i);}for (int i=0; ii) {scanf ("%d%d", &qu[i].l, &qu[i].r);qu[i].id = i;}memset (cnt, 0, sizeof(cnt));solve();for (int i=0; ii) {printf ("%d\n", ans[i]);}}return 0;
}
/*
4 2
15 10 6 7
1 3
2 4
*/

5. 情人节的阻击 (lyf)

这种xjb题目区域赛经常会出

分成两类讨论：

一类是贴角放，尽量放成正方形的；

另外就是沿着短一点的边放

#include
using namespace std;
int n, m, x, y;int work(int x) {int f = sqrt(x);if (f*f>=x) return 2*f;if (f*(f+1)>=x) return 2*f+1;return 2*(f+1);
}int main () {//freopen("5.in", "r", stdin);//freopen("5.out", "w", stdout);while (~scanf("%d%d%d%d", &n,&m,&x,&y)) {if (n>m) swap(n, m);if (x>y) swap(x, y);int ans1 = 0;if (x/n < 1) ans1 = x + 1;else ans1 = (x%n>0) + n;printf ("%d\n", min(ans1, work(x)));}return 0;
}
/*
1 2 1 12 4 2 62 4 4 43 4 4 83 4 3 9
*/

6.男生女生配（lyf）

树状数组

灵儿当时来问了这题这么做，感觉看着对话可能更容易理解：

其实就是因为每个点和它左下角的点的曼哈顿距离可以通过：x1+y1 - (xi+yi)来求

总体复杂度：O((n+m)*log(200000))

#include
using namespace std;
const int M = 200000+10;
const int DJ = 200000+1;
const int inf = 0x3f3f3f3f;
int n, m;
struct Node {int x, y, tp, id;
}a[M<<1];
int ans[M];int c[M];
void init() {memset(c, -1, sizeof(c[0])*M);
}
void ins(int x,int v) {for (int i=x; i max(c[i], v);
}
int ask(int x) {int ret = -1;for (int i=x; i>0; i-=i&-i) ret = max(ret, c[i]);return ret;
}
void change() {for (int i=0; ii) {int tmp = a[i].x;a[i].x = DJ-a[i].y;a[i].y = tmp;}
}bool cmp(const Node &a,const Node &b) {if (a.x==b.x) {if (a.y==b.y) return a.tp<b.tp;return a.y<b.y;}return a.x<b.x;
}
void update() {init();sort(a, a+n+m, cmp);for (int i=0; ii) {if (a[i].tp==0) {ins(a[i].y, a[i].x+a[i].y);} else {int ret = ask(a[i].y);if (ret!=-1) ans[a[i].id] = min(ans[a[i].id], a[i].x+a[i].y-ret);}}
}int main () {//freopen("6.in", "r", stdin);//freopen("6.out", "w", stdout);while (~scanf("%d", &n)) {for (int i=0; ii) {scanf ("%d%d", &a[i].x,&a[i].y);a[i].tp = 0;}scanf("%d", &m);for (int i=0; ii) {scanf ("%d%d", &a[i+n].x,&a[i+n].y);a[i+n].tp = 1;a[i+n].id = i;}memset(ans, inf, sizeof(ans[0])*m);for (int i=0; i<4; ++i) {if (i) change();update();}for (int i=0; ii) {printf ("%d\n", ans[i]);}//printf ("%d\n", ans[0]);
    }return 0;
}
/*
2
1 1
3 3
1
2 4
*/

7.光梯(Noland)

有题意可知，对最后一个点造成影响的点是它前面k个点点，如果知道他前面k个点的期望，在求出每个点走到最后一个点走到这个点的概率，那么就可以求出最后一个点的期望，
如何求出前k个点走到最后一个点所占的比率，假设已知前n-1个点的期望，当只能走到下标为n-k的点时，将会有1/k的部分走到最后一个点，当只能走到下标为n-k+1的点时，还
剩余整体的（k-1）/k,然后又1/(k-1)的概率走到最后一个点，然后可以知道每个点走到最后一个点的概率都是1/k，所有就是前k个点的和除以k，因为这题n和q比较大，但是k比
较小，可以先打表得到所有的值，然后对于询问直接输出即可。

#include
using namespace std;
const int N = 1e5+7;
const int M = 107;
double dp[M][N];
void  init(){memset(dp,0,sizeof(dp));for(int i = 1;i < M;i ++){double sum = 0;for(int j = 1;j < N;j ++){sum += dp[i][j-1];int res = min(i,j);if(j > i){sum -= dp[i][j-min(i,j)-1];}dp[i][j] = sum / min(i,j)+1;}}
}int main(){init();freopen("7.in","r",stdin);freopen("7.out","w",stdout);int n,k;while(scanf("%d %d",&n,&k)==2){printf("%.3f\n",dp[k][n]);}return 0;
}

8.magic number（xufei）

看着题目，其实很容易发现 小于等于 S 的都是magic, 然后对于大于 S的，最多只要往上跑 9*9 暴力判就好了，因为1e9里内所有位的和最大值撑死也就 81

9.科学计数法

比赛的时候，我一直在想，为啥大家都怼着A，不做这题。。。。。

10.我好方

我连公式都给了啊！！！为什么还有wa的！！！！

11.不要方

这道题其实是个面试题

我们把矩形的四条边称作(上，下，左，右),

然后对于(上1，上2）选靠下边的线，对于（下1，下2）选靠上边的线

对于(左1，左2）选靠右的线，对于（右1，右2）选靠左的线

然后只要这新的四条线，有交集，那个交集的面积就是答案了。

（PS:其实因为数据很小，你暴力模拟染色技术也能过）

12.丢手绢(baobao)

你把正n边形，和正n-1边形随便找个点拆开来，铺成一条线，然后很容易发现规律。。。。

然后比赛的时候有人用 O(1e9)过了，好像还是我们学校的小伙子，hhhh

具体证明如下：

假设现在有两种点，第一种点是有n个点的，第二种有n-1个点的，假设这两种点的第一个点是重合的，很容易证第2种点的第i个在第1种点的第i个和第i+1之间，在第二种点中，当i小于（n+1）/2时，距离它最近的第一种点事第i个点，当i大于（n+1）/2时，距离它最近的点事第i+1个点，当i等于（n+1）/2时，它距离第i个和第i+1个点的距离是相同的，可以发现每个点离得最近的点没有重复的，所有每个点移动到它最近的点就好了，计算距离的时候，当i小于（n+1）/2时，距离他最近的点的距离是(i-1)/(n*(n-1))，这就是一个等差数列，大于（n+1）/2的点也一样，然后等差数列求和就好了。

#include
using namespace std;
typedef long long ll;
const double eps = 1e-9;
ll n;int main () {while (~ scanf("%lld", &n)) {if (n<=2) {puts("0");continue;}double x = 1.0/n, y = 1.0/(n-1);ll f = (n-1)/2;double ans = (1+f)*f/2.0*(y-x)*2;//cout << ans << endl;ans -=  0.5 - 1.0/n*(n/2);printf ("%.0f\n", ans*1000+eps);}return 0;
}

转载于:https://www.cnblogs.com/get-an-AC-everyday/p/8022554.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！