Educational Codeforces Round 145 (Rated for Div. 2) (A~E)

Problem – B – Codeforces

Thoughts:

  1. After we choose the length, its specific length will form a square, because the distance between points is greater than 1, so even-numbered squares can only contain even-numbered squares, and odd-numbered ones contain odd numbers.
  2. Compute the maximum number of points each length holds:
    1. Found that cnt[0]=1, cnt[2]=9, cnt[4]=25
    2. cnt[1]=4, cnt[3]=16, cnt[5]=36.
    3. It is found that the maximum length n accommodates points is (n + 1)^{2}

So for a given n, we find the root sign to get ans, if ans*ans==n-1, the answer is ans. Otherwise (that is, ans*ans 

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\\
"
#define int long long
#define endll endl<<endl
typedef unsigned long long ull;
typedef pair<long long, long long> pll;
//------------------------------------------------ -------------------------------------------------- -------------------//
//------------------------------------------------ -------------------------------------------------- -------------------//
const int INF = 0x3f3f3f3f; //int type INF
const ll llINF = 0x3f3f3f3f3f3f3f3f;//ll type llINF

void mysolve()
{
int n;
cin>>n;
int ans=sqrt(n);
if (ans*ans==n)ans--;
cout<<ans<<endl;
}
int32_t main()
{
std::ios::sync_with_stdio(0), cin. tie(0), cout. tie(0);
ll t;
cin >> t;
while (t--)
{
mysolve();
}
system("pause");
return 0;
}

Problem – C – Codeforces

Thoughts:

We try to make up 2, 2, 2, 2, x,-1000,-1000

  1. We now gather i 2s in front, then there is currently \frac{(i + 1)*i}{2} integers, and \frac{( i + 1)*i}{2}<=k.
  2. When the collected i is the largest, it is obvious that adding i+1 positive numbers to the i+1 next will exceed k. First let k-(i+1)*i/2.
  3. Then, instead of making up a negative number, he and the sub-array just constitute the remaining k integers, then his value is -2*(i-k). Of course, one of them will be 0 when written in this way, so we add 1 to ensure that an integer will not be added, and a 0 will not be neutralized.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\\
"
#define int long long
#define endll endl<<endl
typedef unsigned long long ull;
typedef pair<long long, long long> pll;
//------------------------------------------------ -------------------------------------------------- -------------------//
//------------------------------------------------ -------------------------------------------------- -------------------//
const int INF = 0x3f3f3f3f; //int type INF
const ll llINF = 0x3f3f3f3f3f3f3f3f;//ll type llINF
const int N = 2e5 + 10;

void mysolve()
{
int n,k;
cin>>n>>k;
vector<int>v;
for (int i=1; i<=n; + + i)
{
if (k-i>=0)
{
k-=i;
v.push_back(2);
}
else if (k>0)
{
v.push_back(-2*(i-k) + 1);
k=0;
}
else
{
v.push_back(-1000);
}
}
for (int i=0; i<n; + + i)cout<<v[i]<<" ";
cout<<endl;
}

int32_t main()
{
std::ios::sync_with_stdio(0), cin. tie(0), cout. tie(0);
ll t;
cin >> t;
while (t--)
{
mysolve();
}
system("pause");
return 0;
}

Problem – D – Codeforces

The very intuitive one is direct dp, and the other is to observe that the exchange is at most once, and the rest are deleted

Thought 1: DP

dp[i][0] indicates completion to i subscript, and its end is 0

dp[i][1] indicates that the end is 1

dp[i][2] means that the end is 1 and there is more than one 1 in the string (the case of only one 1 is not considered here)

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\\
"
#define int long long
#define endll endl<<endl
typedef unsigned long long ull;
typedef pair<long long, long long> pll;
//------------------------------------------------ -------------------------------------------------- -------------------//
//------------------------------------------------ -------------------------------------------------- -------------------//
const int INF = 0x3f3f3f3f; //int type INF
const ll llINF = 0x3f3f3f3f3f3f3f3f;//ll type llINF
const int N = 3e5 + 10;
int dp[N][5];
void mysolve()
{
string s;
cin>>s;
int len=(int)s. size();
int a=1e12,b=a + 1;
for (int i=0; i<=len; + + i)dp[i][0]=dp[i][1]=dp[i][2]=llINF;
dp[0][0]=0;
for (int i=1; i<=len; + + i)
{
if (s[i-1]=='0')
{
dp[i][0]=dp[i-1][0];
dp[i][1]=dp[i-1][1] + a;//Originally there was a 1, which can be exchanged
dp[i][2]=dp[i-1][2] + b;//Originally there were multiple 1s, so this 0 should be deleted
}
else
{
dp[i][0]=dp[i-1][0] + b;//The front is all 0, here 1 should be deleted
dp[i][1]=dp[i-1][0];//The front is all 0, so as to ensure that there is only one 1 after the last 1 is put in
dp[i][2]=min(dp[i-1][1],dp[i-1][2]);
}
}
int ans=min(dp[len][0],min(dp[len][1],dp[len][2]));
cout<<ans<<endl;
}

int32_t main()
{
std::ios::sync_with_stdio(0), cin. tie(0), cout. tie(0);
ll t;
cin >> t;
while (t--)
{
mysolve();
}
system("pause");
return 0;
}

Thought 2: Observe that there is at most one exchange, and the rest will be deleted

  1. If we exchange 2 times or more, it means that his exchange must have continuous elements in the end, so it is better for me to delete the continuous exchange.
  2. The case where the exchange contributes is only the case where s[i]=0 & amp; & amp;s[i-1]=1, so we traverse n to find if there is such a situation, and exchange it once if there is one, leaving the previous 1 Delete all with the following 0
  3. We can use the prefix and record the number of 1
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\\
"
#define int long long
#define endll endl<<endl
typedef unsigned long long ull;
typedef pair<long long, long long> pll;
//------------------------------------------------ -------------------------------------------------- -------------------//
//------------------------------------------------ -------------------------------------------------- -------------------//
const int INF = 0x3f3f3f3f; //int type INF
const ll llINF = 0x3f3f3f3f3f3f3f3f;//ll type llINF
const int N = 3e5 + 10;
int cnt[N];
void mysolve()
{
string s;
cin>>s;
ll ans=llINF,b=1e12 + 1;
int n=(int)s. size();
cnt[0]=(s[0]=='1');
for (int i=1; i<n; + + i)cnt[i]=cnt[i-1] + (s[i]=='1');
for (int i=0; i<n; + + i)
{
int cnt1=cnt[i-1], cnt0=n-i-1-(cnt[n-1]-cnt[i]);
if (i>0 & amp; & amp;s[i]=='0' & amp; & amp;s[i-1]=='1')ans=min(ans,b* (cnt1 + cnt0)-1);//cnt[i-1] 1 number before subscript i, n-i-(cnt[n-1]-cnt[i]), 0 numbers after subscript i
else ans=min(ans,b*(cnt1 + cnt0));
}
cout<<ans<<endl;
}

int32_t main()
{
std::ios::sync_with_stdio(0), cin. tie(0), cout. tie(0);
ll t;
cin >> t;
while (t--)
{
mysolve();
}
system("pause");
return 0;
}

Problem-E-Codeforces

Thoughts: Simulation to determine the upper and lower limits

  1. Because the sum of the water in the two cups will not change, we can discuss the situation based on the sum, traversing (0,a + b), then cup a takes at least l=min(0,i-b) each time, and takes at most r=max(a,i)
  2. If the number in the middle has not overflowed, record the sum of operations. Then if there is no overflow, then the initial is j, and the answer is j-sum.
  3. Obviously, each operation is the boundary that is most likely to overflow, so we only need to discuss how much the left boundary takes at least and the right boundary takes at least after all the operations on the left and right boundaries.
    1. Obviously, if the number taken in the middle overflows the left boundary once, it means that it is assimilated with the left boundary, then its subsequent operation should be the same as the value of the left boundary, and its final value is the final value of the left boundary
    2. Similarly, if the middle number overflows the right boundary once, then it is assimilated by the right boundary, and the answer is the value of the right boundary
    3. If there is no overflow on the left and right, congratulations that he is cornered, he can only take j-sum (j is the starting value of the first cup)
  4. So there are only 3 answers, at least take the final value of the left boundary lo (it will be this value if you come to the left boundary at least once), and take at most the final value of the right boundary hi (you will be this value if you come to the right boundary at least once). Otherwise, if a boundary does not go, only j-sum
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\\
"
#define int long long
#define endll endl<<endl
const int N = 1e3 + 10;

int v[N*10];
int ans[N][N];
void mysolve()
{
int n,a,b;
cin>>n>>a>>b;
int sum=0;
for (int i=1; i<=n; + + i)cin>>v[i], sum + =v[i];
for (int i=0; i<=a + b; + + i)
{
int l=max(0ll,i-b),r=min(a,i);
int lo=l,hi=r;
for (int j=1; j<=n; + + j)
{
lo=max(min(lo-v[j],r),l);//Update the left boundary
hi=min(max(hi-v[j],l),r);//Update the right boundary
}
for (int j=l; j<=r; + + j)ans[j][i-j]=max(lo,min(hi,j-sum));
}
for (int i=0; i<=a; + + i)for (int j=0; j<=b; + + j)cout<<ans[i][j]<<" \\
\ "[j==b];
//The new line-wrapping posture learned, " \\
"[] is an array, if the brackets are false, take the array [0], if it is true, take the array [1]
}
int32_t main()
{
std::ios::sync_with_stdio(0), cin. tie(0), cout. tie(0);
mysolve();
system("pause");
return 0;
}