A. City Day
time limit per test1 second memory limit per test256 megabytes
For years, the Day of city N was held in the most rainy day of summer. New mayor decided to break this tradition and select a not-so-rainy day for the celebration. The mayor knows the weather forecast for the n days of summer. On the i-th day, a_i millimeters of rain will fall. All values a_i are distinct.
The mayor knows that citizens will watch the weather x days before the celebration and y days after. Because of that, he says that a day d is not-so-rainy if a_d is smaller than rain amounts at each of x days before day d and and each of y days after day d. In other words, a_d < a_j should hold for all\( d - x \le j < d and d < j \le d + y.\) Citizens only watch the weather during summer, so we only consider such j that \(1 \le j \le n\).
Help mayor find the earliest not-so-rainy day of summer.Input
The first line contains three integers n, x and\( y (1 \le n \le 100\,000, 0 \le x, y \le 7) \)— the number of days in summer, the number of days citizens watch the weather before the celebration and the number of days they do that after.
The second line contains n distinct integers \(a_1, a_2, ..., a_n (1 \le a_i \le 10^9)\), where a_i denotes the rain amount on the i-th day.Output
Print a single integer — the index of the earliest not-so-rainy day of summer. We can show that the answer always exists.ExamplesinputCopy
10 2 2 10 9 6 7 8 3 2 1 4 5
outputCopy
3
inputCopy
10 2 3 10 9 6 7 8 3 2 1 4 5
outputCopy
8
inputCopy
5 5 5 100000 10000 1000 100 10
outputCopy
5
Note
In the first example days 3 and 8 are not-so-rainy. The 3-rd day is earlier.
In the second example day 3 is not not-so-rainy, because 3 + y = 6 and a_3 > a_6. Thus, day 8 is the answer. Note that 8 + y = 11, but we don't consider day 11, because it is not summer.
签到
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e6+100;
int n,x,y,a[maxn];
int main(){
scanf("%d%d%d",&n,&x,&y);
rep(i,1,n) scanf("%d",&a[i]);
rep(i,1,n){
int l=max(1,i-x);
int r=min(n,i+y);
int flag=1;
rep(j,l,r) if(j!=i&&a[j]<=a[i]){flag=0;break;}
if(flag){
return printf("%d\n",i),0;
}
}
}
B. Water Lily
time limit per test1 second memory limit per test256 megabytes
While sailing on a boat, Inessa noticed a beautiful water lily flower above the lake's surface. She came closer and it turned out that the lily was exactly H centimeters above the water surface. Inessa grabbed the flower and sailed the distance of L centimeters. Exactly at this point the flower touched the water surface.
Suppose that the lily grows at some point A on the lake bottom, and its stem is always a straight segment with one endpoint at point A. Also suppose that initially the flower was exactly above the point A, i.e. its stem was vertical. Can you determine the depth of the lake at point A?Input
The only line contains two integers H and \(L (1 \le H < L \le 10^{6})\).Output
Print a single number — the depth of the lake at point A. The absolute or relative error should not exceed \(10^{-6}\).
Formally, let your answer be A, and the jury's answer be B. Your answer is accepted if and only if \(\frac{|A - B|}{\max{(1, |B|)}} \le 10^{-6}\).ExamplesinputCopy
1 2
outputCopy
1.5000000000000
inputCopy
3 5
outputCopy
2.6666666666667
签到
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e6+100;
ll h,l;
int main(){
scanf("%lld%lld",&h,&l);
printf("%.12lf\n",(l*l-h*h)/(2.0*h));
}
A. MP3
time limit per test1 second memory limit per test256 megabytes
One common way of digitalizing sound is to record sound intensity at particular time moments. For each time moment intensity is recorded as a non-negative integer. Thus we can represent a sound file as an array of n non-negative integers.
If there are exactly K distinct values in the array, then we need\( k = \lceil \log_{2} K \rceil\) bits to store each value. It then takes nk bits to store the whole file.
To reduce the memory consumption we need to apply some compression. One common way is to reduce the number of possible intensity values. We choose two integers \(l \le r\), and after that all intensity values are changed in the following way: if the intensity value is within the range [l;r], we don't change it. If it is less than l, we change it to l; if it is greater than r, we change it to r. You can see that we lose some low and some high intensities.
Your task is to apply this compression in such a way that the file fits onto a disk of size I bytes, and the number of changed elements in the array is minimal possible.
We remind you that 1 byte contains 8 bits.
\(k = \lceil log_{2} K \rceil\) is the smallest integer such that \(K \le 2^{k}\). In particular, if K = 1, then k = 0.Input
The first line contains two integers n and \(I (1 \le n \le 4 \cdot 10^{5}, 1 \le I \le 10^{8})\) — the length of the array and the size of the disk in bytes, respectively.
The next line contains n integers\( a_{i} (0 \le a_{i} \le 10^{9})\) — the array denoting the sound file.Output
Print a single integer — the minimal possible number of changed elements.ExamplesinputCopy
6 1 2 1 2 3 4 3
outputCopy
2
inputCopy
6 2 2 1 2 3 4 3
outputCopy
0
inputCopy
6 1 1 1 2 2 3 3
outputCopy
2
Note
In the first example we can choose l=2, r=3. The array becomes 2 2 2 3 3 3, the number of distinct elements is K=2, and the sound file fits onto the disk. Only two values are changed.
In the second example the disk is larger, so the initial file fits it and no changes are required.
In the third example we have to change both 1s or both 3s.
模拟题，注意一下先判断掉显然答案为0的情况，否则会爆int
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(auto i=(a);i<=(b);++i)
#define dep(i,a,b) for(auto i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e6+100;
const int mod=(int)1e9+7;
int n;
ll a[maxn],k,pre[maxn];
map<ll,ll> mp;
set<ll> s;
int main(){
scanf("%d%lld",&n,&k);k*=8;
rep(i,1,n) scanf("%lld",&a[i]),s.insert(a[i]),mp[a[i]]++;
if(k/n>31) return puts("0"),0;
ll lim=1ll<<(k/n),cnt=(ll)s.size();
ll ans=0;
if(cnt<=lim) return puts("0"),0;
int pos=0;
for(auto u:s) pos++,pre[pos]=pre[pos-1]+mp[u];
rep(i,0,n-lim) ans=max(ans,pre[i+lim]-pre[i]);
printf("%lld\n",n-ans);
}
B. Welfare State
time limit per test2 seconds memory limit per test256 megabytes
There is a country with n citizens. The i-th of them initially has a_{i} money. The government strictly controls the wealth of its citizens. Whenever a citizen makes a purchase or earns some money, they must send a receipt to the social services mentioning the amount of money they currently have.
Sometimes the government makes payouts to the poor: all citizens who have strictly less money than x are paid accordingly so that after the payout they have exactly x money. In this case the citizens don't send a receipt.
You know the initial wealth of every citizen and the log of all events: receipts and payouts. Restore the amount of money each citizen has after all events.Input
The first line contains a single integer \(n (1 \le n \le 2 \cdot 10^{5}) \)— the numer of citizens.
The next line contains n integers \(a_1, a_2, ..., a_n (0 \le a_{i} \le 10^{9})\) — the initial balances of citizens.
The next line contains a single integer \(q (1 \le q \le 2 \cdot 10^{5})\) — the number of events.
Each of the next q lines contains a single event. The events are given in chronological order.
Each event is described as either 1 p \(x (1 \le p \le n, 0 \le x \le 10^{9})\), or 2 x \((0 \le x \le 10^{9})\). In the first case we have a receipt that the balance of the p-th person becomes equal to x. In the second case we have a payoff with parameter x.Output
Print n integers — the balances of all citizens after all events.ExamplesinputCopy
4 1 2 3 4 3 2 3 1 2 2 2 1
outputCopy
3 2 3 4
inputCopy
5 3 50 2 1 10 3 1 2 0 2 8 1 3 20
outputCopy
8 8 20 8 10
Note
In the first example the balances change as follows: \(1 2 3 4 \rightarrow 3 3 3 4 \rightarrow 3 2 3 4 \rightarrow 3 2 3 4\)
In the second example the balances change as follows:\( 3 50 2 1 10 \rightarrow 3 0 2 1 10 \rightarrow 8 8 8 8 10 \rightarrow 8 8 20 8 10\)
真正的乱搞题，很显然每个2操作只对于在和他前面最近的2操作之间的1操作有改变
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(auto i=(a);i<=(b);++i)
#define dep(i,a,b) for(auto i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e6+100;
const int mod=(int)1e9+7;
int n,a[maxn],vis[maxn];
struct node{
int op,pos,val,x;
}p[maxn];
int main(){
scanf("%d",&n);
rep(i,1,n) scanf("%d",&a[i]);
int q;scanf("%d",&q);
rep(i,1,q){
scanf("%d",&p[i].op);
if(p[i].op==1) scanf("%d%d",&p[i].pos,&p[i].val);
else scanf("%d",&p[i].x);
}
int pre=0;
dep(i,q,1){
if(p[i].op==1) p[i].val=max(p[i].val,pre);
else pre=max(pre,p[i].x);
}
rep(i,1,q) if(p[i].op==1){
a[p[i].pos]=p[i].val;vis[p[i].pos]=1;
}
rep(i,1,n){
printf("%d ",vis[i]?a[i]:max(a[i],pre));
}
}
C. Matching vs Independent Set
time limit per test1 second memory limit per test256 megabytes
You are given a graph with \(3 \cdot n\) vertices and m edges. You are to find a matching of n edges, or an independent set of n vertices.
A set of edges is called a matching if no two edges share an endpoint.
A set of vertices is called an independent set if no two vertices are connected with an edge.Input
The first line contains a single integer \(T \ge 1\) — the number of graphs you need to process. The description of T graphs follows.
The first line of description of a single graph contains two integers n and m, where \(3 \cdot n\) is the number of vertices, and m is the number of edges in the graph\( (1 \leq n \leq 10^{5}, 0 \leq m \leq 5 \cdot 10^{5})\).
Each of the next m lines contains two integers \(v_i and u_i (1 \leq v_i, u_i \leq 3 \cdot n)\), meaning that there is an edge between vertices v_i and u_i.
It is guaranteed that there are no self-loops and no multiple edges in the graph.
It is guaranteed that the sum of all n over all graphs in a single test does not exceed \(10^{5}\), and the sum of all m over all graphs in a single test does not exceed \(5 \cdot 10^{5}\).Output
Print your answer for each of the T graphs. Output your answer for a single graph in the following format.
If you found a matching of size n, on the first line print "Matching" (without quotes), and on the second line print n integers — the indices of the edges in the matching. The edges are numbered from 1 to m in the input order.
If you found an independent set of size n, on the first line print "IndSet" (without quotes), and on the second line print n integers — the indices of the vertices in the independent set.
If there is no matching and no independent set of the specified size, print "Impossible" (without quotes).
You can print edges and vertices in any order.
If there are several solutions, print any. In particular, if there are both a matching of size n, and an independent set of size n, then you should print exactly one of such matchings or exactly one of such independent sets.ExampleinputCopy
4 1 2 1 3 1 2 1 2 1 3 1 2 2 5 1 2 3 1 1 4 5 1 1 6 2 15 1 2 1 3 1 4 1 5 1 6 2 3 2 4 2 5 2 6 3 4 3 5 3 6 4 5 4 6 5 6
outputCopy
Matching 2 IndSet 1 IndSet 2 4 Matching 1 15
Note
The first two graphs are same, and there are both a matching of size 1 and an independent set of size 1. Any of these matchings and independent sets is a correct answer.
The third graph does not have a matching of size 2, however, there is an independent set of size 2. Moreover, there is an independent set of size 5: 2 3 4 5 6. However such answer is not correct, because you are asked to find an independent set (or matching) of size exactly n.
The fourth graph does not have an independent set of size 2, but there is a matching of size 2.
大胆猜想必定有解；
其实看到一个3n就能想到这个结论，因为如果存在一个matching的话那就存在2n个不同的点，如果存在一个indset的话就存在n个不同的点，加起来正好是3n；
做法就是，枚举每条边，如果这条边的两个端点没有被访问过就加入答案，否则不加，看看加入的边数是否大于等于n即可；
如果是的，那么就直接输出，否则必定存在大于等于n个点未被范围，构成一个indset
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(auto i=(a);i<=(b);++i)
#define dep(i,a,b) for(auto i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e6+100;
const int mod=(int)1e9+7;
int n,m,vis[maxn];
void solve(){
scanf("%d%d",&n,&m);
rep(i,0,3*n) vis[i]=0;
vector<int> v;
rep(i,1,m){
int a,b;scanf("%d%d",&a,&b);
if(vis[a]==0&&vis[b]==0){
vis[a]=vis[b]=1;v.pb(i);
}
}
if((int)v.size()>=n){
puts("Matching");int pos=1;
for(auto u:v) if(pos<=n) printf("%d ",u),pos++;
}else{
puts("IndSet");int pos=1;
rep(i,1,3*n) if(pos<=n&&vis[i]==0) printf("%d ",i),pos++;
} puts("");
}
int main(){
int T;cin>>T;
while(T--) solve();
}
D. Rectangle Painting 1
time limit per test1 second memory limit per test256 megabytes
There is a square grid of size \(n \times n\). Some cells are colored in black, all others are colored in white. In one operation you can select some rectangle and color all its cells in white. It costs \(\max(h, w)\) to color a rectangle of size\( h \times w\). You are to make all cells white for minimum total cost.Input
The first line contains a single integer \(n (1 \leq n \leq 50)\) — the size of the square grid.
Each of the next n lines contains a string of length n, consisting of characters '.' and '#'. The j-th character of the i-th line is '#' if the cell with coordinates (i, j) is black, otherwise it is white.Output
Print a single integer — the minimum total cost to paint all cells in white.ExamplesinputCopy
3 ### #.# ###
outputCopy
3
inputCopy
3 ... ... ...
outputCopy
0
inputCopy
4 #... .... .... #...
outputCopy
2
inputCopy
5 #...# .#.#. ..... .#... #....
outputCopy
5
Note
The examples and some of optimal solutions are shown on the pictures below.
n=50，暴搜
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(auto i=(a);i<=(b);++i)
#define dep(i,a,b) for(auto i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e6+100;
const int mod=(int)1e9+7;
int n,dp[55][55][55][55];
char s[55][55];
int dfs(int x,int y,int xx,int yy){
if(dp[x][y][xx][yy]!=-1) return dp[x][y][xx][yy];
if(x==xx&&y==yy) return dp[x][y][xx][yy]=(s[x][y]=='#');
int ans=max(xx-x+1,yy-y+1);
rep(i,x,xx-1) ans=min(ans,dfs(x,y,i,yy)+dfs(i+1,y,xx,yy));
rep(i,y,yy-1) ans=min(ans,dfs(x,y,xx,i)+dfs(x,i+1,xx,yy));
return dp[x][y][xx][yy]=ans;
}
int main(){
scanf("%d",&n);
rep(i,1,n) scanf("%s",s[i]+1);
memset(dp,-1,sizeof(dp));
printf("%d\n",dfs(1,1,n,n));
}
E. Rectangle Painting 2
time limit per test1 second memory limit per test256 megabytes
There is a square grid of size \(n \times n\). Some cells are colored in black, all others are colored in white. In one operation you can select some rectangle and color all its cells in white. It costs \min(h, w) to color a rectangle of size \(h \times w\). You are to make all cells white for minimum total cost.
The square is large, so we give it to you in a compressed way. The set of black cells is the union of m rectangles.Input
The first line contains two integers n and \(m (1 \le n \le 10^{9}, 0 \le m \le 50)\) — the size of the square grid and the number of black rectangles.
Each of the next m lines contains 4 integers \(x_{i1} y_{i1} x_{i2} y_{i2} (1 \le x_{i1} \le x_{i2} \le n, 1 \le y_{i1} \le y_{i2} \le n)\) — the coordinates of the bottom-left and the top-right corner cells of the i-th black rectangle.
The rectangles may intersect.Output
Print a single integer — the minimum total cost of painting the whole square in white.ExamplesinputCopy
10 2 4 1 5 10 1 4 10 5
outputCopy
4
inputCopy
7 6 2 1 2 1 4 2 4 3 2 5 2 5 2 3 5 3 1 2 1 2 3 2 5 3
outputCopy
3
Note
The examples and some of optimal solutions are shown on the pictures below.
网络流经典模型；
显然我们可以把问题简化为：需要最少多少的行和列能将所有格子覆盖；
我们建立一个二分图，将x坐标视为左部的点，y坐标视为右部的点，一个黑色格子就表示一条边（二分图经典模型），那么解决上述问题只要求最小点匹配，也就是最大匹配，即可；
但是我们发现点数可以有1e9，显然是不行的，这时候又是另一个经典模型，用最大流去求最大匹配；
具体方法就是把左部的所有点都连接到超级源点，右部的所有点都连到超级汇点，然后跑最大流即可；
这道题就是这样，我们只需要把左部点和超级源点的边权设置为行（或列）的宽度即可
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(auto i=(a);i<=(b);++i)
#define dep(i,a,b) for(auto i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
const int mod=(int)1e9+7;
const int inf=(int)1e9;
int n,m,vis[110][110],lx[110],ly[110],px,py;
struct que{int x1,x2,y1,y2;}a[110];
int tot=1,head[maxn<<1],dep[maxn],iter[maxn],Q[maxn],S,T;
struct node{int u,v,nxt,w;}g[maxn<<1];
void add(int u,int v,int w){g[++tot]={u,v,head[u],w};head[u]=tot;g[++tot]={v,u,head[v],0};head[v]=tot;}
int bfs(){
rep(i,1,T) dep[i]=0,iter[i]=head[i];
int ql=0,qr=0;Q[++qr]=S;dep[S]=1;
while(ql<qr){
int x=Q[++ql];
for(int i=head[x];i;i=g[i].nxt) if(!dep[g[i].v]&&g[i].w) dep[g[i].v]=dep[x]+1,Q[++qr]=g[i].v;
}
return dep[T];
}
int dfs(int x,int f){
if(x==T||!f) return f;
int sf=0;
for(int i=iter[x];i;i=g[i].nxt) if(dep[g[i].v]==dep[x]+1&&g[i].w){
int w=dfs(g[i].v,min(g[i].w,f));
if(f) {g[i].w-=w;g[i^1].w+=w;f-=w;sf+=w;}
}
return sf;
}
int dinic(){
int ans=0;while(bfs()) ans+=dfs(S,inf);
return ans;
}
int main(){
scanf("%d%d",&n,&m);
rep(i,1,m){
scanf("%d%d%d%d",&a[i].x1,&a[i].y1,&a[i].x2,&a[i].y2);a[i].x2++;a[i].y2++;
lx[++px]=a[i].x1;lx[++px]=a[i].x2;ly[++py]=a[i].y1;ly[++py]=a[i].y2;
}sort(lx+1,lx+1+px);sort(ly+1,ly+1+py);
px=unique(lx+1,lx+1+px)-lx;py=unique(ly+1,ly+1+py)-ly;
S=px+py+1;T=S+1;
rep(i,1,px-2) add(S,i,lx[i+1]-lx[i]);
rep(i,1,py-2) add(px+i,T,ly[i+1]-ly[i]);
rep(i,1,m){
int x1=lower_bound(lx+1,lx+1+px,a[i].x1)-lx,x2=lower_bound(lx+1,lx+1+px,a[i].x2)-lx;
int y1=lower_bound(ly+1,ly+1+py,a[i].y1)-ly,y2=lower_bound(ly+1,ly+1+py,a[i].y2)-ly;
rep(x,x1,x2-1) rep(y,y1,y2-1) if(!vis[x][y]) vis[x][y]=1,add(x,px+y,inf);
} printf("%d\n",dinic());
}
