# 2017年浙江工业大学大学生程序设计迎新赛预赛

A

```#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <utility>
#include <bitset>

using namespace std;
#define LL long long
#define pb push_back
#define mk make_pair
#define fi first
#define se second
#define lson (rt << 1)
#define rson ((rt << 1) | 1)
#define pill pair<int, int>
#define mst(a, b)   memset(a, b, sizeof a)
#define REP(i, x, n)    for(int i = x; i <= n; ++i)
const int MOD = 1e9 + 7;
const int qq = 1e5 + 10;
const int INF = 1e9 + 10;
int num[qq];

int main(){
int t;  scanf("%d", &t);
while (t--) {
int n, k;   scanf("%d%d", &n, &k);
int ans = 0;
for (int i = 0; i < n; ++i) {
scanf("%d", num + i);
ans ^= num[i];
}
if (ans == 0 || (num[k - 1] < (num[k - 1] ^ ans))) {
puts("No");
} else {
puts("Yes");
}
}
return 0;
}```

B

```#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <utility>
#include <bitset>

using namespace std;
#define LL long long
#define pb push_back
#define mk make_pair
#define fi first
#define se second
#define lson (rt << 1)
#define rson ((rt << 1) | 1)
#define pill pair<int, int>
#define mst(a, b)   memset(a, b, sizeof a)
#define REP(i, x, n)    for(int i = x; i <= n; ++i)
const int MOD = 1000000007;
const int qq = 1e5 + 10;
const int INF = 1e9 + 10;
string st;
map<LL, LL> mp;
LL ct = 0;
void get(int &i) {
LL a, b, tmp = 1;
a = b = 0;
if (st[i] == '-')   tmp = -1, ++i;
else if (st[i] == '+')  ++i;
if (st[i] == 'x') {
a = tmp * 1;
} else if (isdigit(st[i])) {
while (isdigit(st[i])) {
a = a * 10 + st[i++] - '0';
}
a = a * tmp;
}
if (st[i] == 'x') {
i++;
if (st[i] == '^') {
i++;
while (isdigit(st[i])) {
b = b * 10 + st[i++] - '0';
}
} else {
b = 1;
}
}
if (mp.find(b) == mp.end()) {
mp[b] = a;
} else {
mp[b] += a;
}
}
LL quickPow(LL a, LL b) {
LL ans = 1;
while (b > 0) {
if (b & 1)  ans = (ans * a) % MOD;
a = (a * a) % MOD;
b >>= 1;
}
return ans;
}

int main(){
ios::sync_with_stdio(false);
while (cin >> st) {
int len = st.size(), i = 0;
while (i < len) {
get(i);
}
map<LL, LL>::iterator it;
int t;  cin >> t;
while (t--) {
LL x;   cin >> x;
x %= MOD;
LL ans = ct;
for (it = mp.begin(); it != mp.end(); ++it) {
ans = (ans + (it->second * (quickPow(x, it->first)) % MOD + MOD) % MOD + MOD) % MOD;
}
cout << ans << endl;
}
mp.clear();
ct = 0;
}
return 0;
}```

C

```#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <utility>
#include <bitset>

using namespace std;
#define LL long long
#define pb push_back
#define mk make_pair
#define fi first
#define se second
#define lson (rt << 1)
#define rson ((rt << 1) | 1)
#define pill pair<int, int>
#define mst(a, b)   memset(a, b, sizeof a)
#define REP(i, x, n)    for(int i = x; i <= n; ++i)
const int MOD = 1e9 + 7;
const int qq = 1e5 + 10;
const int INF = 1e9 + 10;
LL fin[qq];
LL quickPow(LL a, LL b) {
LL ans = 1;
while (b > 0) {
if(b & 1)   ans = (ans * a) % MOD;
b >>= 1;
a = (a * a) % MOD;
}
return ans;
}
void Init() {
fin[0] = 1;
for (int i = 1; i < qq; ++i) {
fin[i] = (1LL * i * fin[i - 1]) % MOD;
}
}
map<LL, LL> mp;
LL num[qq];
LL n, m;
void solve(LL a, LL b) {
a = mp[a];
LL ans = (fin[b] * quickPow((fin[a] * fin[b - a]) % MOD, MOD - 2) ) % MOD;
printf("%lld\n", num[(ans % n) + 1]);
}
int main(){
Init();
int t;  scanf("%d", &t);
while (t--) {
mp.clear();
scanf("%lld%lld", &n, &m);
for (int i = 1; i <= n; ++i) {
scanf("%lld", num + i);
mp[num[i]] = i;
}
while (m--) {
LL a, b;    scanf("%lld%lld", &a, &b);
solve(a, b);
}
}
return 0;
}```

D

```#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <utility>
#include <bitset>

using namespace std;
#define LL long long
#define pb push_back
#define mk make_pair
#define fi first
#define se second
#define lson (rt << 1)
#define rson ((rt << 1) | 1)
#define pill pair<int, int>
#define mst(a, b)   memset(a, b, sizeof a)
#define REP(i, x, n)    for(int i = x; i <= n; ++i)
const int MOD = 1e9 + 7;
const int qq = 1e5 + 10;
const int INF = 1e9 + 10;
int tmp[qq];
void solve (int n, int m) {
deque<int> Q, tm;
deque<int>::iterator it;
int a, b;
int f = 0;
for (int i = 0; i < m; ++i) {
scanf("%d", &a);
if (a == 1) {
scanf("%d", &b);
if (!f) Q.push_front(b);
else    Q.push_back(b);
} else if(a == 2) {
if (!f) Q.pop_front();
else    Q.pop_back();
} else if(a == 3) {
scanf("%d", &b);
if (!f) Q.push_back(b);
else    Q.push_front(b);
} else if(a == 4) {
if(!f)  Q.pop_back();
else    Q.pop_front();
} else if(a == 5) {
f ^= 1;
} else if(a == 6) {
printf("%d\n", (int)Q.size());
int cnt = 0;
for (it = Q.begin(); it != Q.end(); ++it) {
tmp[cnt++] = *it;
}
if (!f) {
for (int i = 0; i < cnt; ++i) {
printf("%d%c", tmp[i], i == cnt - 1 ? '\n' : ' ');
}
} else {
for (int i = cnt - 1; i >= 0; --i) {
printf("%d%c", tmp[i], i == 0 ? '\n' : ' ');
}
}
} else if(a == 7) {
int cnt = 0;
for (it = Q.begin(); it != Q.end(); ++it) {
tmp[cnt++] = *it;
}
Q.clear();
sort(tmp, tmp + cnt);
for(int i = 0; i < cnt; ++i) {
if(!f)  Q.push_back(tmp[i]);
else    Q.push_front(tmp[i]);
}
}
}
}

int main(){
int n, m;   scanf("%d%d", &n, &m);
solve(n, m);
return 0;
}```

E

```#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <utility>
#include <bitset>

using namespace std;
#define LL long long
#define pb push_back
#define mk make_pair
#define fi first
#define se second
#define lson (rt << 1)
#define rson ((rt << 1) | 1)
#define pill pair<int, int>
#define mst(a, b)   memset(a, b, sizeof a)
#define REP(i, x, n)    for(int i = x; i <= n; ++i)
const int MOD = 1e9 + 7;
const int qq = 6e6;
const LL INF = 1e9 + 10;
struct Node {
LL l, r;
}p[qq];
int n, k;
LL mid;
bool cmp(const Node &a, const Node &b) {
return a.l - mid * a.r > b.l - mid * b.r;
}
bool check() {
sort(p, p + n, cmp);
LL tmp = 0;
for (int i = 0; i < k; ++i) {
tmp += (p[i].l - mid * p[i].r);
}
//  printf("%lld %lld\n", mid, tmp);
//  printf("%lld\n", tmp >= 0);
if (tmp >= 0)    return true;
return false;
}

int main(){
int t;  scanf("%d", &t);
while (t--) {
scanf("%d%d", &n, &k);
for (int i = 0; i < n; ++i) {
scanf("%lld%lld", &p[i].r, &p[i].l);
}
LL l = 0, r = 1e8, ans = 0;
while (l <= r) {
mid = (l + r) >> 1;
if (check() == true) {
ans = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
printf("%lld\n", ans);
}
return 0;
}```

F

```#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <utility>
#include <bitset>

using namespace std;
#define LL long long
#define pb push_back
#define mk make_pair
#define fi first
#define se second
#define lson (rt << 1)
#define rson ((rt << 1) | 1)
#define pill pair<int, int>
#define mst(a, b)   memset(a, b, sizeof a)
#define REP(i, x, n)    for(int i = x; i <= n; ++i)
const int MOD = 1e9 + 7;
const int qq = 1e5 + 10;
const int INF = 1e9 + 10;
int n, m, k, s;
int p[qq], dis[qq];
bool vis[qq];
vector<int> G[qq];
void spfa() {
mst(vis, false);
queue<int> Q;
vis[s] = true;
mst(dis, 0x3f3f3f3f);
//  printf("%d\n", dis[0]);
dis[s] = 0;
Q.push(s);
while (!Q.empty()) {
int u = Q.front();
Q.pop();
vis[u] = false;
for (int i = 0; i < (int)G[u].size(); ++i) {
int v = G[u][i];
if (dis[u] + 1 < dis[v]) {
dis[v] = dis[u] + 1;
if(vis[v])  continue;
vis[v] = true;
Q.push(v);
}
}
}
}

int main(){
while (scanf("%d%d%d%d", &n, &m, &k, &s) != EOF) {
for (int i = 1; i <= k; ++i) {
scanf("%d", p + i);
}
for (int a, b, i = 0; i < m; ++i) {
scanf("%d%d", &a, &b);
G[a].pb(b);
G[b].pb(a);
}
spfa();
int minx = INF;
for (int i = 1; i <= k; ++i) {
if(i >= dis[p[i]])   minx = min(minx, i);
}
minx = min(minx, max(dis[p[k]], k));
printf("%d\n", minx);
for (int i = 0; i <= n; ++i) {
G[i].clear();
}
}
return 0;
}```

G

```#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <utility>
#include <bitset>

using namespace std;

#define LL long long
#define pb push_back
#define mk make_pair
#define pill pair<int, int>
#define mst(a, b) memset(a, b, sizeof a)

const int qq = 1e5 + 10;
const int INF = 1e9 + 10;
const int MOD = 1e9 + 7;
int stk[qq][2];
int ans[qq];

int main() {
int t;	scanf("%d", &t);
int Cas = 0;
while (t--) {
int top = 0;
int n;	scanf("%d", &n);
mst(ans, 0);
for (int x, i = 1; i <= n; ++i) {
scanf("%d", &x);
if (!top) {
stk[++top][0] = i;
stk[top][1] = x;
} else {
while (top && stk[top][1] < x) {
ans[i]--;
ans[stk[top][0]]++;
top--;
}
if (top) {
ans[i]--;
ans[stk[top][0]]++;
}
stk[++top][0] = i;
stk[top][1] = x;
}
}
int maxn = 0, id;
for (int i = 1; i <= n; ++i) {
ans[i] += ans[i - 1];
if (ans[i] > maxn) {
maxn = ans[i];
id = i;
}
}
printf("Case #%d: %d %d\n", ++Cas, id + 1, maxn);
}
return 0;
} ```

H

```#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <utility>
#include <bitset>

using namespace std;
#define LL long long
#define pb push_back
#define mk make_pair
#define fi first
#define se second
#define lson (rt << 1)
#define rson ((rt << 1) | 1)
#define pill pair<int, int>
#define mst(a, b)   memset(a, b, sizeof a)
#define REP(i, x, n)    for(int i = x; i <= n; ++i)
const int MOD = 1e9 + 7;
const int qq = 1e5 + 10;
const int INF = 1e9 + 10;
int maxn[qq * 4], lazy[qq * 4], a[qq];
void pushUp(int rt) {
maxn[rt] = max(maxn[lson], maxn[rson]);
}
void pushDown(int rt) {
if (lazy[rt]) {
maxn[lson] += lazy[rt];
maxn[rson] += lazy[rt];
lazy[lson] += lazy[rt];
lazy[rson] += lazy[rt];
lazy[rt] = 0;
}
}
void build(int l, int r, int rt) {
lazy[rt] = 0;
if (l == r) {
maxn[rt] = a[l];
return;
}
int mid = (l + r) >> 1;
build(l, mid, lson);
build(mid + 1, r, rson);
pushUp(rt);
}
int first(int l, int r, int rt) {
if (l == r) {
return l;
}
pushDown(rt);
int mid = (l + r) >> 1;
int res;
if (maxn[lson] > 0)  res = first(l, mid, lson);
else    res = first(mid + 1, r, rson);
pushUp(rt);
return res;
}
int get(int p, int l, int r, int rt) {
if (l == r) {
return maxn[rt];
}
pushDown(rt);
int res;
int mid = (l + r) >> 1;
if (p <= mid)    res = get(p, l, mid, lson);
else    res = get(p, mid + 1, r, rson);
pushUp(rt);
return res;
}
void upDate(int x, int y, int val, int l, int r, int rt) {
if (x <= l && r <= y) {
maxn[rt] += val;
lazy[rt] += val;
return;
}
pushDown(rt);
int mid = (l + r) >> 1;
if (x <= mid)    upDate(x, y, val, l, mid, lson);
if (y > mid) upDate(x, y, val, mid + 1, r, rson);
pushUp(rt);
}

int main(){
int t;  scanf("%d", &t);
while (t--) {
int n;  scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d", a + i);
}
sort(a + 1, a + 1 + n);
build(1, n, 1);
for (int i = n; i >= 1; --i) {
int y = first(1, n, 1);
if (y >= i)  break;
int x = get(i, 1, n, 1);
if (x >= i - y) {
upDate(y, i - 1, -1, 1, n, 1);
upDate(i, i, -(i - y), 1, n, 1);
} else {
upDate(i, i, -x, 1, n, 1);
upDate(i - x, i - 1, -1, 1, n, 1);
if (get(i - x - 1, 1, n, 1) > get(i - x, 1, n, 1)) {
int L1 = i - x - 1, R1 = i - x - 1, L2 = i - x, R2 = i - x;
int left = y, right = i - x - 1;
while (left <= right) {
int mid = (left + right) >> 1;
if (get(mid, 1, n, 1) < get(i - x - 1, 1, n, 1)) {
left = mid + 1;
} else {
right = mid - 1;
L1 = mid;
}
}
left = i - x, right = i - 1;
while (left <= right) {
int mid = (left + right) >> 1;
if (get(mid, 1, n, 1) > get(i - x, 1, n, 1)) {
right = mid - 1;
} else {
left = mid + 1;
R2 = mid;
}
}
if (R1 - L1 == R2 - L2) {
upDate(L1, R1, -1, 1, n, 1);
upDate(L2, R2, 1, 1, n, 1);
} else if (R1 - L1 > R2 - L2) {
upDate(L2, R2, 1, 1, n, 1);
upDate(L1, L1 + (R2 - L2), -1, 1, n, 1);
} else {
upDate(L1, R1, -1, 1, n, 1);
upDate(R2 - (R1 - L1), R2, 1, 1, n, 1);
}
}
}
/*for (int j = 1; j <= i; ++j) {
printf("%d ", get(j, 1, n, 1));
}
puts("");*/
}
LL ans = 0;
for (int i = 1; i <= n; ++i) {
//          printf("%d\n", get(i, 1, n, 1));
ans += (LL)get(i, 1, n, 1);
}
printf("%lld\n", ans);
}
return 0;
}```

I

```#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <utility>
#include <bitset>

using namespace std;
#define LL long long
#define pb push_back
#define mk make_pair
#define fi first
#define se second
#define lson (rt << 1)
#define rson ((rt << 1) | 1)
#define pill pair<int, int>
#define mst(a, b)   memset(a, b, sizeof a)
#define REP(i, x, n)    for(int i = x; i <= n; ++i)
const int MOD = 1e9 + 7;
const int qq = 1e5 + 10;
const int INF = 1e9 + 10;
int num[qq];

int main(){
int n;  scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
if(i % 4 == 0)  continue;
bool f = false;
int tm = i;
while (tm > 0) {
if(tm % 10 == 4)    f = true;
tm /= 10;
}
if(f)   continue;
printf("%d\n", i);
}
return 0;```

J

```#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <utility>
#include <bitset>

using namespace std;
#define LL long long
#define pb push_back
#define mk make_pair
#define fi first
#define se second
#define lson (rt << 1)
#define rson ((rt << 1) | 1)
#define pill pair<int, int>
#define mst(a, b)   memset(a, b, sizeof a)
#define REP(i, x, n)    for(int i = x; i <= n; ++i)
const int MOD = 1e9 + 7;
const int qq = 1e3 + 10;
const int INF = 1e9 + 10;
const double PI = 4.0 * atan(1.0);
double r, c, R;
int n;
double x[qq], y[qq];
double check(double a) {
int t = a;
if (t == 0) {
double tm = a;
for (int i = 0; i < 2; ++i) {
tm *= 10;
int b = tm;
b %= 10;
if(b != 0)  return a;
}
return 0;
}
return a;
}

int main(){
int t;  scanf("%d", &t);
while (t--) {
scanf("%lf%lf%lf%d", &r, &c, &R, &n);
double gap = 2.0 * PI / n;
double init = 0.0;
for (int i = 0; i < n; ++i) {
x[i] = R * cos(init);
y[i] = R * sin(init);
init += gap;
}
printf("%.2lf %.2lf\n", check(x[0] + r), check(y[0] + c));
for (int i = n - 1; i >= 1; --i) {
printf("%.2lf %.2lf\n", check(x[i] + r), check(y[i] + c));
}
}
return 0;
}```

K

```#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <utility>
#include <bitset>

using namespace std;
#define LL long long
#define pb push_back
#define mk make_pair
#define fi first
#define se second
#define lson (rt << 1)
#define rson ((rt << 1) | 1)
#define pill pair<int, int>
#define mst(a, b)   memset(a, b, sizeof a)
#define REP(i, x, n)    for(int i = x; i <= n; ++i)
const int MOD = 1e9 + 7;
const int qq = 1e3 + 10;
const int INF = 1e9 + 10;
int mr[qq][qq];
int num[qq], dis[qq], n;
bool vis[qq];
void solve() {
int ans = 0;
mst(vis, false);
vis[1] = true;
for (int i = 1; i <= n; ++i) {
dis[i] = mr[1][i];
}
for (int i = 1; i < n; ++i) {
int maxn = -1, k;
for (int j = 1; j <= n; ++j) {
if(vis[j])  continue;
if(maxn < dis[j])    maxn = dis[k = j];
}
vis[k] = true;
ans += maxn;
for (int j = 1; j <= n; ++j) {
if(vis[j])  continue;
dis[j] = max(dis[j], mr[k][j]);
}
}
printf("%d\n", ans);
}

int main(){
int t;  scanf("%d", &t);
while (t--) {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d", num + i);
for(int j = 1; j < i; ++j) {
mr[i][j] = mr[j][i] = (num[i] + num[j]) / 2;
}
}
solve();
}
return 0;
}```

L

```#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <utility>
#include <bitset>

using namespace std;
#define LL long long
#define pb push_back
#define mk make_pair
#define fi first
#define se second
#define lson (rt << 1)
#define rson ((rt << 1) | 1)
#define pill pair<int, int>
#define mst(a, b)   memset(a, b, sizeof a)
#define REP(i, x, n)    for(int i = x; i <= n; ++i)
const int MOD = 1e9 + 7;
const int qq = 1e5 + 10;
const int INF = 1e9 + 10;
int num[qq];

int main(){
int t;  scanf("%d", &t);
while (t--) {
for (int i = 0; i < 3; ++i) {
scanf("%d", num + i);
}
int a = max(num[0], max(num[1], num[2]));
int c = min(num[0], min(num[1], num[2]));
int b = num[0] + num[1] + num[2] - a - c;
printf("%d\n", a * 100 + b * 10 + c);
}
return 0;
}```

M

```#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <utility>
#include <bitset>

using namespace std;
#define LL long long
#define pb push_back
#define mk make_pair
#define fi first
#define se second
#define lson (rt << 1)
#define rson ((rt << 1) | 1)
#define pill pair<int, int>
#define mst(a, b)   memset(a, b, sizeof a)
#define REP(i, x, n)    for(int i = x; i <= n; ++i)
const int MOD = 1e9 + 7;
const int qq = 1e5 + 10;
const int INF = 1e9 + 10;
int num[qq];

int main(){
int t;  scanf("%d", &t);
while (t--) {
int n;  scanf("%d", &n);
for (int i = 0; i < n; ++i) {
scanf("%d", num + i);
}
int b;  scanf("%d", &b);
sort(num, num + n);
priority_queue<int, vector<int>, greater<int> > Q;
for (int i = 0; i < n; ++i) {
if (Q.size() < 3) {
Q.push(num[i] + b);
} else {
int u = Q.top();
Q.pop();
if (u <= num[i]) {
Q.push(num[i] + b);
} else {
Q.push(u + b);
}
}
}
int maxn = 0;
while (!Q.empty()) {
maxn = max(maxn, Q.top());
Q.pop();
}
printf("%d\n", maxn);
}
return 0;
}```