Problem - B - Codeforces
思路：
- 我们选择长度后，其特定长度会构成一个正方形，因为点与点距离大于1，所以偶数的正方形里面只能包含偶数的正方形，奇数的包含奇数。
- 计算每个长度容纳最大点数：
- 发现cnt[0]=1,cnt[2]=9,cnt[4]=25
- cnt[1]=4,cnt[3]=16,cnt[5]=36。
- 发现最大长度n容纳点数为
所以对于给定的n，我们求根号得到ans，如果ans*ans==n-1,答案是ans。否则 （即ans*ans<n)是ans，因为得出是ans.小数（即ans可以容纳（ans+1)^2的点数）
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\n"
#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型的INF
const ll llINF = 0x3f3f3f3f3f3f3f3f;//ll型的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
思路：
我们尝试凑成2，2，2，2，x,-1000,-1000的形式
- 我们现在前面凑i个2，那么当前有
个整数，且
- 当凑的i最大时，显然接下来凑第i+1个增加i+1个正数会超过k。先让k-（i+1）*i/2.
- 那么，我们改为凑一个负数，他与子数组刚好构成剩下的k个整数，那么他的值就是-2*(i-k)。当然这样写会有一个是0，所以我们加1，就保证不会增加一个整数，也不会中和出一个0.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\n"
#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型的INF
const ll llINF = 0x3f3f3f3f3f3f3f3f;//ll型的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
很直观的一种是直接dp，另一种是观察出最多交换一次，剩下都是删除
思路1：DP
dp[i][0]表示完成到i下标，其结尾是0
dp[i][1]表示结尾是1
dp[i][2]表示结尾是1且串里面不止一个1（只有一个1的情况不考虑在这里）
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\n"
#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型的INF
const ll llINF = 0x3f3f3f3f3f3f3f3f;//ll型的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;//原来有一个1，可以交换
dp[i][2]=dp[i-1][2]+b;//原来有多个1，那这个0还是删了吧
}
else
{
dp[i][0]=dp[i-1][0]+b;//前面都是0，这里1要删除
dp[i][1]=dp[i-1][0];//前面都是0，才能保证最后一个1放入后只有一个1
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;
}思路2：观察出最多交换一次，剩下都是删除
- 我们如果交换2次及以上，说明他的交换最后必定有连续的成分，那么连续的交换不如我直接删除。
- 交换有贡献的情况只有s[i]=0&&s[i-1]=1的情况，所有我们遍历n寻找是否存在这样的情况，有就交换一次，剩下前面的1与后面的0全部删除
- 我们可以用前缀和记录1的个数
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\n"
#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型的INF
const ll llINF = 0x3f3f3f3f3f3f3f3f;//ll型的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&&s[i]=='0'&&s[i-1]=='1')ans=min(ans,b*(cnt1+cnt0)-1);//cnt[i-1]下标i前面1个数，n-i-(cnt[n-1]-cnt[i]),下标i后面0个数
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
思路：模拟确定上下限
- 因为两个杯子的水的和是不会变的，所以我们可以根据和来讨论情况，遍历(0,a+b),那么杯子a每次最少取l=min(0,i-b),最多取r=max(a,i)
- 如果中间的数没有过上下溢出，记录操作的和。那么不会溢出的话，那么初始为j,答案就是j-sum。
- 显然，每次操作是边界最容易溢出，那么我们只需要讨论左右边界经过所有操作后，左边界至少取多少，右边界至少取多少。
- 显然，中间取的数，如果溢出过一次左边界，等于他与左边界同化了，那么他后续被操作的情况应该与左边界的值一样，那么他最终的值就是左边界最终的值
- 同理，如果中间数溢出过一次右边界，那么他被右边界同化，答案是右边界的值
- 如果左右都没溢出，恭喜他被逼入绝境，他只能取j-sum（j为第一个杯子的起始值）
- 所以答案就3个，最少取左边界最终值lo（至少来过一次左边界就会是这个值），最多取右边界最终值hi（至少来过一次右边界就会是这个值）。不然一个边界没去只能j-sum
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\n"
#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);//更新左边界
hi=min(max(hi-v[j],l),r);//更新右边界
}
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]<<" \n"[j==b];
//学到的换行新姿势，" \n"[]是一个数组,如果括号内为假，取数组[0],为真，取数组[1]
}
int32_t main()
{
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
mysolve();
system("pause");
return 0;
}
