Codeforces_714
2024-09-06 16:03:41
A.相遇时间段l = max(l1,l2),r = min(r1,r2)，再判断k是否在里面。
#include <iostream>
using namespace std; long long l1,l2,r1,r2,k; int main()
{
cin >> l1 >> r1 >> l2 >> r2 >> k;
long long l = max(l1,l2),r = min(r1,r2);
if(l > r) cout << << endl;
else
{
long long t = r-l+;
if(l <= k && k <= r) t--;
cout << t << endl;
}
return ;
}
B.判断出现的数的个数，1或2个直接YES，3个以上直接NO，3个判断是否等差。
#include<bits/stdc++.h>
using namespace std; int n,a[];
map<int,int> mp; int main()
{
ios::sync_with_stdio(false);
cin >> n;
int cnt = ;
for(int i = ;i <= n;i++)
{
int x;
cin >> x;
if(!mp.count(x))
{
cnt++;
mp[x] = ;
a[cnt] = x;
}
}
if(cnt == || cnt == ) cout << "YES" << endl;
else if(cnt >= ) cout << "NO" << endl;
else
{
sort(a+,a+);
if(a[]+a[] == *a[]) cout << "YES" << endl;
else cout << "NO" << endl;
}
return ;
}
C.把每一个数都转换成18位的pattern串，放进map处理。
#include<bits/stdc++.h>
using namespace std; int n;
map<string,int> mp; int main()
{
ios::sync_with_stdio(false);
cin >> n;
while(n--)
{
string s1,s2,s = "";
cin >> s1 >> s2;
for(int i = s2.length()-;i >= ;i--)
{
if((s2[i]-'')%) s = ""+s;
else s = ""+s;
}
while(s.length() < ) s = ""+s;
if(s1 == "+") mp[s]++;
else if(s1 == "-") mp[s]--;
else cout << mp[s] << endl;
}
return ;
}
D.先把图分成左右或上下两块，然后二分每一块中矩形的四条边。
#include<bits/stdc++.h>
using namespace std; int n;
struct xx
{
long long x1,x2,y1,y2;
void print()
{
cout << x1 << " " << y1 << " " << x2 << " " << y2 << " ";
}
}; int query(int x1,int y1,int x2,int y2)
{
if(x1 > x2)swap(x1,x2);
if(y1 > y2)swap(y1,y2);
cout<<"? "<<x1<<" "<<y1<<" "<<x2<<" "<<y2<<endl;
int ans;
cin>>ans;
return ans;
} xx f(int x1,int y1,int x2,int y2)
{
xx ans;
long long l = x1,r = x2;
while(l < r)
{
int mid = (l+r)/;
if(query(x1,y1,mid,y2) < ) l = mid+;
else r = mid;
}
ans.x2 = l;
l = x1,r = x2;
while(l < r)
{
int mid = (l+r+)/;
if(query(mid,y1,x2,y2) < ) r = mid-;
else l = mid;
}
ans.x1 = l;
l = y1,r = y2;
while(l < r)
{
int mid = (l+r)/;
if(query(x1,y1,x2,mid) < ) l = mid+;
else r = mid;
}
ans.y2 = l;
l = y1,r = y2;
while(l < r)
{
int mid = (l+r+)/;
if(query(x1,mid,x2,y2) < ) r = mid-;
else l = mid;
}
ans.y1 = l;
return ans;
}
int main()
{
cin >> n;
long long x1,y1,x2,y2,x3,y3,x4,y4;
long long l = ,r = n;
while(l < r)
{
long long mid = (l+r)/;
if(query(,,mid,n) < ) l = mid+;
else r = mid;
}
long long t = l;
if(query(,,t,n) == && query(t+,,n,n) == )
{
xx a = f(,,t,n),b = f(t+,,n,n);
cout << "! ";
a.print();
b.print();
cout << endl;
return ;
}
l = ,r = n;
while(l < r)
{
long long mid = (l+r)/;
if(query(,,n,mid) < ) l = mid+;
else r = mid;
}
t = l;
xx a = f(,,n,t),b = f(,t+,n,n);
cout << "! ";
a.print();
b.print();
cout << endl;
return ;
}
E.如果是非严格单调递增该如何做，我们会发现每次调整，都是调整某个数字为原先数列中存在的数字，最后才是最优的，所以，我们设DP[i][j]表示前i个数字，最后一个数为原先数列排序后第j大的数字的最小代价，然后令a[i]=a[i]-i，把严格单调递增就转化为非严格单调递增。
#include<bits/stdc++.h>
using namespace std; int n;
long long a[],b[],dp[][]; int main()
{
cin >> n;
for(int i = ;i <= n;i++)
{
cin >> a[i];
a[i] -= i;
b[i] = a[i];
}
sort(b+,b++n);
for(int i = ;i <= n;i++)
{
long long minn = dp[i-][];
for(int j = ;j <= n;j++)
{
minn = min(minn,dp[i-][j]);
dp[i][j] = abs(a[i]-b[j])+minn;
}
}
long long ans = dp[n][];
for(int i = ;i <= n;i++) ans = min(ans,dp[n][i]);
cout << ans << endl;
return ;
}
还有优先队列优化的。
#include<bits/stdc++.h>
using namespace std; int n;
priority_queue<long long> q; int main()
{
cin >> n;
long long ans = ;
for(int i = ;i <= n;i++)
{
long long x;
cin >> x;
x -= i;
q.push(x);
if(q.top() > x)
{
ans += q.top()-x;
q.pop();
q.push(x);
}
}
cout << ans << endl;
return ;
}
最新文章
- phpcms 表单提交发送邮件
- Redis应用场景一
- SGA(System Global Area)
- 【原创】kafka controller源代码分析(一)
- JavaScript_Html5_LocalStorage项目demo
- mongodb的备份
- Oracle 10g Block Change Tracking特性
- RHCS集群
- Linux设备驱动程序：中断处理之顶半部和底半部
- 正确的使用枚举（Enum）
- C++14介绍
- Cisco Packet Tracer做单臂路由的过程
- 修改GDAL库支持RPC像方改正模型
- 工具(2): 极简MarkDown排版介绍（How to）
- POJ 1988 Cube Stacking 【带权并查集】
- 21 python的魔法方法（转）
- 用.NET CORE做项目，VS里编译碰到‘。。。。包降级。。。。’错误
- P3273 [SCOI2011]棘手的操作
- 将Json对象数组转化成JS Array数组
- android 所有焦点问题