a
//赛时猜的做法,赛后,赛后补一下。
//其实就是分类讨论;
//首先当有个数组有三个不同的数字,按递增·顺序就好了。
//当两个都是2的时候。有a》b,c》d,按a+c》c+b||a+d》b+d排就ok了
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve(){
int n;
cin>>n;
set<int> a,b;
for(int i=1;i<=n;i++){
int num;
cin>>num;
a.insert(num);
}
for(int i=1;i<=n;i++){
int num;
cin>>num;
b.insert(num);
}
if(a.size()+b.size()>=4){
cout<<"YES\n";
}else{
cout<<"NO\n";
}
}
signed main(){
int t;
cin>>t;
while(t--)
solve();
}
b
//这道题告诉我要多动笔。写样例得出一般规律
//首先对于8,8样例,ans确定,遂于8,7ans是1,6 5 4 3 2 1就不用想了肯定是了
//大胆猜测,对于k小于n,ans就是在某个范围,从小的开始想,首先构造1,肯定在第二数组里面。所以
//通过ok来调整第一个组的大小看能不能构造出1,记住如果1多于ok,那么ans就是2,不然ans就是1.间隔也算
#include <bits/stdc++.h>
using namespace std;
void solve(){
int n,k;
cin>>n>>k;
vector<int> vc(n+1);
for(int i=1;i<=n;i++){
cin>>vc[i];
}
int len=n-k;
int ans=1e9;
if(len)
{
int ok=n-k;
for(int i=2;i<=2+ok;i++){
if(vc[i]!=1) ans=1;
}
ans=min(2,ans);
}
else{
int b=1;
for(int i=2;i<=n;i+=2){
if(vc[i]!=b){
ans=min(b,ans);
}
b++;
}
ans=min(ans,b);
}
cout<<ans<<"\n";
}
int main(){
int t;
cin>>t;
while(t--)
solve();
}
C
//我们尝试构造出12345...,首先想想怎么构造1。发现由///于时间的累加。只有最后一个人是一个人的时候才ok,///然后考虑怎么构造2,由于1的限制,只有另一队列倒数///两个才有1,规律就是数后面1的数量
#include <bits/stdc++.h>
using namespace std;
void solve() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<vector<int>> mat(n, vector<int>(n));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
cin >> mat[i][j];
}
}
vector<int> L(n, 0);
for (int i = 0; i < n; ++i) {
int count = 0;
for (int j = n - 1; j >= 0; --j) {
if (mat[i][j] == 1) {
++count;
} else {
break;
}
}
L[i] = count;
}
sort(L.begin(), L.end());
int mh = 0;
for (int x : L) {
if (x >= mh + 1) {
++mh;
}
}
mh = min(mh, n - 1);
cout << mh + 1 << endl;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}
D
//二维dijk,发现,只要走到相同的边,那么就有最小代价;
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int INF = 0x3f3f3f3f;
void solve(){
int n, a, b;
cin >> n >> a >> b;
vector<vector<int>> edge1(n+1), edge2(n+1);
int m1;
cin >> m1;
set<pii> se;
for (int i = 0; i < m1; i++){
int u, v;
cin >> u >> v;
edge1[u].emplace_back(v);
edge1[v].emplace_back(u);
se.insert({v, u});
se.insert({u, v});
}
int m2;
cin >> m2;
map<int,int> mp;
for (int i = 0; i < m2; i++){
int u, v;
cin >> u >> v;
edge2[u].emplace_back(v);
edge2[v].emplace_back(u);
if (se.count({u, v}) || se.count({v, u})){
mp[v]++;
mp[u]++;
}
}
vector<vector<int>> dis(n+1, vector<int>(n+1, INF));
vector<vector<bool>> vis(n+1, vector<bool>(n+1, false));
dis[a][b] = 0;
priority_queue< tuple<int,int,int>, vector<tuple<int,int,int>>, greater<tuple<int,int,int>> > que;
que.push({0, a, b});
while(!que.empty()){
auto [d, p1, p2] = que.top();
que.pop();
if(vis[p1][p2]) continue;
vis[p1][p2] = true;
for(auto d1 : edge1[p1]){
for(auto d2 : edge2[p2]){
if(dis[d1][d2] > d + abs(d1 - d2)){
dis[d1][d2] = d + abs(d1 - d2);
que.push({dis[d1][d2], d1, d2});
}
}
}
}
int ans = INF;
for(auto &pr : mp){
int i = pr.first;
ans = min(ans, dis[i][i]);
}
if(ans >= INF){
cout << -1 << "\n";
} else {
cout << ans << "\n";
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while(t--){
solve();
}
return 0;
}
A
//观察发现有多少个1有是几
//证明:最多cnt个1就可以转化完成。
//由于每次都是选择相邻不同的,那么说明就是只肯能是间隔,且最优10101也至是减少1,
//所以最优
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve(){
string n;
cin>>n;
int cnt=0;
for(auto c:n){
if(c=='1') cnt++;
}
cout<<cnt<<"\n";
}
signed main(){
int t;
cin>>t;
while(t--){
solve();
}
}
B
//贪婪的想,对于每个状态,从当前点出发后到左(右)的时间乘以2都得到达
//不然就是错误
//因为假设我们最优选择了一个点,这个点必定要左和右,那么他必须经得住时间
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve(){
int n;
cin>>n;
vector<int> vc(n+1);
bool tag=true;
for(int i=1;i<=n;i++){
cin>>vc[i];
if(vc[i]<=2*max(i-1,n-i)){
tag=false;
}
}
if(tag)
cout<<"YES\n";
else
cout<<"NO\n";
}
signed main(){
int t;
cin>>t;
while(t--){
solve();
}
}
C
//考虑所有的可能值,发现操作1不会改变初始大小。但是会改变差分的符号
//总是把所有可能列出来
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve(){
int n;
cin>>n;
vector<int> vc(n+1);
int sum=0;
for(int i=1;i<=n;i++){
cin>>vc[i];
sum+=vc[i];
}
if(n==2){
sum=max({sum,vc[2]-vc[1],vc[1]-vc[2]});
}
int op=1;
int mmin=1e9;
int mmax=-1e9;
for(int i=1;i<=n-1;i++){
int temp=0;
for(int j=1;j<=n-i;j++)
{
vc[j]=vc[j+1]-vc[j];
temp+=vc[j];
mmax=max(temp,mmax);
mmin=min(mmin,temp);
}
}
cout<<max({sum,mmax,-mmin})<<"\n";
}
signed main(){
int t;
cin>>t;
while(t--){
solve();
}
}
A
//理解题意且相邻两个数不互质就好
#include <bits/stdc++.h>
using namespace std;
void solve(){
int n,m;
cin>>n>>m;
if(n==m&&n==1){
cout<<1<<"\n";
}else{
cout<<m-n<<"\n";
}
}
int main(){
int t;
cin>>t;
while(t--){
solve();
}
}
B
//观察题意发现是一个限定的取值问题(在左边中间选和右边中间选),可以用//优先队列很好的解决
// Problem: A. Minimal Coprime
// Contest: Codeforces - Codeforces Round 1000 (Div. 2)
// URL: https://codeforces.com/contest/2063/problem/A
// Memory Limit: 256 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve(){
int n,l,r;
cin>>n>>l>>r;
vector<int> vc(n);
for(int i=0;i<n;i++) cin>>vc[i];
priority_queue<int> pq;
for(int i=l-1;i<r;i++){
pq.push(vc[i]);
}
for(int i=0;i<l-1;i++){
if(vc[i]<pq.top()){
pq.pop();
pq.push(vc[i]);
}
}
int ans1=0;
while(pq.size()){
ans1+=pq.top();
pq.pop();
}
for(int i=l-1;i<r;i++){
pq.push(vc[i]);
}
for(int i=r;i<n;i++){
if(vc[i]<pq.top()){
pq.pop();
pq.push(vc[i]);
}
}
int ans2=0;
while(pq.size()){
ans2+=pq.top();
pq.pop();
}
cout<<min(ans1,ans2)<<"\n";
}
signed main(){
int t;
cin>>t;
while(t--){
solve();
}
}
C
没de出来