A. Architecture
如果行最大值中的最大值和列最大值中的最大值不同的话, 那么一定会产生矛盾, 可以手模一个样例看看.
当满足行列最大值相同条件的时候, 就可以判定了.
因为其余的地方一定可以构造出来符合条件的值, 行列是很多的, 填 0 就好了.
- #include<bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- int main()
- {
- int n, m; cin>> n>> m;
- int t1, t2;
- t1 = t2 = 0;
- for(int i = 1, x; i <= n; i++)
- {
- scanf("%d", &x);
- t1 = max(t1, x);
- }
- for(int i = 1, x; i <= m; i++)
- {
- scanf("%d", &x);
- t2 = max(t2, x);
- }
- if(t1 == t2) puts("possible");
- else puts("impossible");
- return 0;
- }
- B. Bracket Sequence https://www.jisuanke.com/contest/8192/428101
用栈模拟即可, 注意要取模
- const int N = 300000 + 5;
- const int mod = 1e9 + 7;
- ll st[N], top, cnt;
- int n;
- char op[20];
- ll get(char *s){
- int len = strlen(s);
- ll x = 0;
- for(int i=0;i<len;i++) x = x * 10 + s[i] - '0';
- return x;
- }
- int main() {
- scanf("%d",&n);
- for(int i=1;i<=n;i++){
- scanf("%s",op);
- if(op[0] == '(') {
- cnt ++;
- st[++top] = -1;
- continue;
- }
- else if(op[0] == ')'){
- if(st[top] == -1) {
- top --;
- continue;
- }
- ll x = st[top];
- while(top>= 2 && st[top-1] != -1){
- if(cnt % 2 == 0)x = (st[top-1] + x)%mod;
- else x = st[top-1] * x % mod;
- top--;
- }
- cnt --;
- top -= 2;
- st[++top] = x;
- }
- else{
- ll x = get(op);
- st[++top] = x;
- }
- }
- ll res = 0;
- while(top) res = (res + st[top--]) % mod;
- printf("%lld\n", res);
- return 0;
- }
- C. Canyon Crossing https://www.jisuanke.com/contest/7190/402304
二分一下最低高度, 然后整个图变成了 n*m 个点, 边权为 0 或 1 的图, 第一排为起点, 最后一排为终点, 跑最短路即可, 由于边权只有 0 和 1, 所以用双端队列维护即可
- const int N = 1000 + 5;
- #define mk make_pair
- int n, m, k, a[N][N];
- int d[N][N],c[N][N];
- int dx[4] = {1,-1,0,0}, dy[4] = {0,0,1,-1};
- pair<int,int> q[2000010];
- bool check(int mid){
- memset(d, 0x3f, sizeof d);
- int l = 1000005,r = 1000004;
- for(int j=1;j<=m;j++)q[++r] = mk(0,j), d[0][j] = 0;
- while(l<=r){
- auto t = q[l++];
- int x = t.first, y = t.second;
- for(int i=0;i<4;i++){
- int nx = x + dx[i], ny = y + dy[i];
- if(nx <1 || nx> n || ny <1 || ny> m)continue;
- if(a[nx][ny]>= mid){
- if(d[nx][ny]> d[x][y]){
- d[nx][ny] = d[x][y];
- q[--l] = mk(nx,ny);
- }
- }else{
- if(d[nx][ny]> d[x][y] + 1){
- d[nx][ny] = d[x][y] + 1;
- q[++r] = mk(nx,ny);
- }
- }
- }
- }
- for(int i=1;i<=m;i++)if(d[n][i] <= k) return true;
- return false;
- }
- int main() {
- scanf("%d%d%d",&n,&m,&k);
- int l = inf, r = 0;
- for(int i=1;i<=n;i++){
- for(int j=1;j<=m;j++){
- scanf("%d",&a[i][j]);
- l = min(l, a[i][j]);
- r = max(r, a[i][j]);
- }
- }
- while(l <r){
- int mid = l + r + 1>> 1;
- if(check(mid))l = mid;
- else r = mid - 1;
- }
- printf("%d\n",l);
- return 0;
- }
- D. Deceptive Dice https://www.jisuanke.com/contest/8192/428103
\(ans\) 为 \(i-1\) 轮的期望, 设 \(t = \lfloor ans \rfloor\) , 那么第 \(i\) 轮的期望是
\[ \frac{t}{n} * ans + \frac{\sum_{t+1}^{n}i}{n} \]
前面的表示有 \(t/n\) 的概率小于等于 ans, 那么第 i 次就不再掷色子. 后面的就是取 [i+1, n] 的期望
- const int N = 100 + 5;
- int n, m;
- double ans;
- int get(int x){return x*(x+1) / 2;}
- int main() {
- scanf("%d%d",&n,&m);
- ans = 1.0 * get(n) / n;
- for(int i=2;i<=m;i++){
- int t = ans;
- ans = 1.0 * t / n * ans + 1.0 * (get(n) - get(t)) / n;
- }
- printf("%.7f\n",ans);
- return 0;
- }
- E. Exits in Excess
这个题有个关键的性质在于无自环.
设两个集合 \(S,T\).
考虑一条边 \(<x,y>\), 如果 \(x<y\), 将这条边插入 \(S\); 否则插入 \(T\).
输出边集大小较小的集合.
- #include<bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- vector<int> t1, t2;
- int n, m;
- int main()
- {
- cin>> n>> m;
- for(int i = 1, x, y; i <= m; i++)
- {
- scanf("%d%d", &x, &y);
- if(x <y) t1.push_back(i);
- else t2.push_back(i);
- }
- if(t1.size()>t2.size()) t1 = t2;
- cout <<t1.size() << endl;
- for(auto x : t1)
- printf("%d\n", x);
- return 0;
- }
- F. Floor Plan
- int n;
- int main() {
- cin>> n;
- int flag = false;
- for(int i=2;i*i<=n;i++){
- if(n % i == 0){
- int res = n / i;
- if((res + i)%2 == 0){
- flag = true;
- int a = (res + i) / 2;
- int b = res - a;
- printf("%d %d\n",b, a);
- break;
- }
- }
- }
- if(!flag) puts("impossible");
- return 0;
- }
- G. Greetings!
- const int N = 100000 + 5;
- char s[N];
- int main() {
- cin>> s;
- int n = strlen(s);
- printf("h");
- for(int i=0;i<2*(n-2);i++)printf("e");
- printf("y");
- return 0;
- }
- I. Inquiry I
- const int N = 1000000 + 5;
- ll a[N], b[N], sa[N], sb[N];
- int n;
- int main() {
- scanf("%d",&n);
- for(int i=1;i<=n;i++)scanf("%lld",&a[i]),b[i] = a[i]*a[i];
- ll res = 0;
- for(int i=1;i<=n;i++) sa[i] = sa[i-1] + a[i], sb[i] = sb[i-1] + b[i];
- for(int i=0;i<=n;i++){
- res = max(res, sb[i] * (sa[n] - sa[i]));
- }
- printf("%lld\n",res);
- return 0;
- }
- K. Knapsack Packing
首先排个序, 最小的一定是 0(空集产生的和), 然后次小的就是集合中最小的数了. 之后每次找到一个新的数字 (即最终答案集合中的数字), 都用它与之前所有组合出来的数字进行求和, 将这些新的数字填入到一个集合中, 再接下来的扫描过程中, 如果发现有该集合的数字, 则一定不是答案集合中的数字, 将其从集合中删除即可.
- const int N = 300000 + 5;
- int n, m, a[N];
- multiset<int> st, tmp;
- map<int,int> mp;
- vector<int> res;
- int main() {
- scanf("%d",&n);
- m = 1 <<n;
- for(int i=1;i<=m;i++)scanf("%d",&a[i]);
- sort(a+1,a+1+m);
- if(a[1] != 0){
- puts("impossible");
- return 0;
- }
- int cnt = 0;
- for(int i=2;i<=m;i++){
- if(mp[a[i]]){
- mp[a[i]] --;
- continue;
- }else{
- cnt ++;
- res.push_back(a[i]);
- for(auto x:st){
- tmp.insert(x + a[i]);
- }
- for(auto x : tmp) {
- st.insert(x);
- mp[x] ++;
- }
- st.insert(a[i]);
- tmp.clear();
- }
- if(cnt> n){
- puts("impossible");
- return 0;
- }
- }
- sort(res.begin(),res.end());
- for(auto x : res)printf("%d\n",x);
- return 0;
- }
- L. Lifeguards https://www.jisuanke.com/contest/8192/428111
将点按照坐标轴排序, 找到中间的点, 对于 n 的奇偶进行分别处理.
n 为奇数则构造一个几乎平行于 y 轴且通过中间点的直线, 可以想到做这条直线的垂直平分线可以将所有点分成两半
n 为偶数则构造一个几乎平行于 y 轴且不通过中间点的直线, 这样的直线的垂直平分线也同样会把所有点分成两半
- const int N = 100000 + 5;
- pair<ll,ll> a[N];
- int n;
- int main() {
- scanf("%d",&n);
- for(int i=1;i<=n;i++) scanf("%lld%lld",&a[i].first, &a[i].second);
- sort(a + 1, a + 1 + n);
- int mid = (n + 1) / 2;
- ll Len = 1000000000000ll;
- ll x = a[mid].first, y = a[mid].second;
- if(n & 1){
- printf("%lld %lld\n", x - Len, y-1);
- printf("%lld %lld\n", x + Len, y+1);
- }else{
- printf("%lld %lld\n", x - Len, y);
- printf("%lld %lld\n", x + Len, y+1);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3462100.html