大意：保證任意2個ai和不等於任意一個ai;
思路：全都是1即可
int T,n;
int main()
{
cin>>T;
while(T--)
{
cin>>n;
rep(i,0,n)
cout<<"1 ";
cout<<"\n";
}
return 0;
}
B. Omkar and Last Class of Math
大意：找到一組a,b，使a+b==n，並且使得lcm(a,b)儘量小
思路:lcm（a,b)儘量小，那b肯定是a的m倍，這樣lcm就是b了，而a+b=n，所以(m+1)/mb=n，b=nm/(m+1)，找到第一個滿足n%(m+1）==0的m值即可，暴力找的話因爲n是1e9，會T，所以用素數篩思想加速一下
ll T,n;
int main()
{
cin>>T;
while(T--)
{
cin>>n;
rep(i,1,sqrt(n)+1)
{
if(n%(i+1)==0)
{
cout<<n-i*n/(i+1)<<" "<<i*n/(i+1)<<"\n";
break;
}
if(i==(int)sqrt(n))
{
cout<<1<<" "<<n-1<<"\n";
}
}
//b=ma
//a+b=n
//(m+1)a=n; (m+1)/m*b=n
//(m+1)b=m*n
//b=m/(m+1)*n
}
return 0;
}
C. Omkar and Baseball
思路：看到這個題，第一反應就是是不是分割區域，以不需要動的點爲間隔，全都是亂的點爲一個區域，找到全都是亂的點的區域個數，輸出，然後打出了這個
int T,n;
int a[maxn];
PII b[maxn];
int cmp(PII a,PII b)
{
if(a.first==b.first)
return a.second<b.second;
return a.first<b.first;
}
int main()
{
cin>>T;
while(T--)
{
cin>>n;
rep(i,0,n)
{
cin>>a[i];
b[i].first=a[i];
b[i].second=i;
}
sort(b,b+n);
int sum=0;
int cnt=0;
rep(i,0,n)
{
if(a[i]==b[i].first && i==b[i].second)
{
if(cnt)
sum++;
cnt=0;
}
else
cnt++;
}
if(cnt)
sum++;
cout<<sum<<"\n";
}
return 0;
}
然後，然後就華麗麗的wa3了，然後思考了下，爲啥不對呢？
哦，假如sum>=3的話，其實完全可以第一次直接動1~n，把他不管之前是啥，排成一個既不是初始狀態，也不是遞增的就行，當n>=3的必然可以，而n<3的時候sum也不能達到3，所以sum的最大值其實就是2，所以在輸出的時候，sum改成min(2,sum)即可
int T,n;
int a[maxn];
PII b[maxn];
int cmp(PII a,PII b)
{
if(a.first==b.first)
return a.second<b.second;
return a.first<b.first;
}
int main()
{
cin>>T;
while(T--)
{
cin>>n;
rep(i,0,n)
{
cin>>a[i];
b[i].first=a[i];
b[i].second=i;
}
sort(b,b+n);
int sum=0;
int cnt=0;
rep(i,0,n)
{
if(a[i]==b[i].first && i==b[i].second)
{
if(cnt)
sum++;
cnt=0;
}
else
cnt++;
}
if(cnt)
sum++;
if(sum<=2)
cout<<sum<<"\n";
else
cout<<2<<"\n";
}
return 0;
}
D. Omkar and Circle
大意：給你一個n長度的陣列，首尾相接，你可以進行（n-1)/2次操作，每次操作[a[i],a[i+1],a[i+2]]替換成[a[i]+a[i+2]]，使最後a[i]最大，問你最大值
分析：每次假如以i爲中心動，那就相當於刪去a[i]，將a[i-1]和a[i+1]合併，而因爲這2者合併了，只能一塊刪去或者保留，所以這(n-1)/2次操作一定不存在相鄰的，假如某次操作是取i，又有次操作是動i+1,那麼a[i]和a[i+1]就會被動2次，這明顯是不合理的，所以每次操作都是至少間隔1， 並且每次操作的本質都是從總和裡刪去a[i]的值，所以問題轉換成了
進行(n-1)/2次操作，每次刪去a[i]的值，每次操作至少間隔1，問這些刪去的a[i]的和最小值
而因爲一共是(n-1)/2次操作，而每次又至少間隔1，設k=(n-1)/2，有k-1次操作是間隔1，1次操作跟之前的是間隔2，列舉哪一位間隔2就行，用字首和還可以進一步加速
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<n;i++)
#define per(i,a,n) for(int i=n-1;i>=a;i--)
typedef long long ll;
typedef double db;
typedef pair<int,int> PII;
typedef vector<int> VI;
const ll mod=1000000007;
const int maxn=200005;
const int inf=0x3f3f3f3f;
const int INF=0x7f7f7f7f;
ll gcd(ll a,ll b){ return b?gcd(b,a%b):a;}
#define ms(a) memset(a,0,sizeof(a))
#define mss(a) memset(a,-1,sizeof(a))
#define msi(a) memset(a,inf,sizeof(a))
#define iossync ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
// head
ll n,m;
long long a[maxn];
long long sum1[maxn];
ll sum2[maxn];
int main()
{
cin>>n;
rep(i,1,n+1)
{
cin>>a[i];
if(i&1)
{//1 3 5
if(i>=3)
sum1[i]=sum1[i-2]+a[i];
else
sum1[i]=a[i];
}
else
{//2 4 6
sum2[i]=sum2[i-2]+a[i];
}
}
if(n==1)
{
cout<<sum1[1]<<"\n";
return 0;
}
m=(n-1)/2;
ll ans=sum2[n-1];
ans=min(ans,sum1[n]-sum1[1]);
ans=min(ans,sum1[n-2]);
for(int i=2;i<=m;i++)
{
ans=min(ans,sum1[2*i-3]+sum2[n-1]-sum2[2*i-2]);
ans=min(ans,sum2[2*i-2]+sum1[n]-sum1[2*i-1]);
}
cout<<sum2[n-1]+sum1[n]-ans<<"\n";
return 0;
}
//選了i，i+1和i-1都不能選了
//（n-1)/2
其實就是個區間dp，n和m最大值才100，水過
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<n;i++)
#define per(i,a,n) for(int i=n-1;i>=a;i--)
typedef long long ll;
typedef double db;
typedef pair<int,int> PII;
typedef vector<int> VI;
const ll mod=1000000007;
const int maxn=200;
const int inf=0x3f3f3f3f;
const int INF=0x7f7f7f7f;
ll gcd(ll a,ll b){ return b?gcd(b,a%b):a;}
#define ms(a) memset(a,0,sizeof(a))
#define mss(a) memset(a,-1,sizeof(a))
#define msi(a) memset(a,inf,sizeof(a))
#define iossync ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
// head
int n,m;
int l,r;
int n1;
int dp1[maxn][maxn],dp2[maxn][maxn];
int dp[maxn][maxn];
int main()
{
cin>>n>>m;
rep(i,1,n+1)
{
cin>>n1;
rep(j,1,n1+1)
{
cin>>l>>r;
rep(z,l,r+1)
{//標記每個點的屬於哪個區域，這裏似乎可以用離散化，直接用標號來確定，emmmm
dp1[i][z]=l;
dp2[i][z]=r;
}
}
}//列 區間dp dp[i][j] dp[i][j] dp[i][k]+dp[k+1][j]+a*a
per(i,1,m+1)
{
rep(j,1,m+1)
{
rep(z,1,j+1)
{
int sum=0;
rep(k,1,n+1)//行
{
// if(check())
if( dp2[k][z]<=j && dp1[k][z]>=i)
{
sum++;
}
// dp[]
}
dp[i][j]=max(dp[i][j],dp[i][z-1]+dp[z+1][j]+sum*sum);
}
}
}
cout<<dp[1][m]<<"\n";
return 0;
}
F. Omkar and Modes
互動題他來啦（cout.flush();）
某人說過，互動題90%都是二分，剩下的10%我也不會
所以這題直接考慮二分
先分析題意，總序列不降，所以每次返回的衆數，以及個數，就是代表在[l,r]這段區間裡，有f個相連的x,
也就是說即使這f個x在最左邊，那也是[l,l+f-1]，在最右邊也是[r-f+1,r]，也就是說[l+f-1,r-f+1]這個區間必然全是x，當然你得滿足l+f-1 < = r-f+1，然後就把這個區域的填補上，再繼續做剩下的區域就好，具體可以看程式碼
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+50;
#define rep(i,a,n) for(int i=a;i<n;i++)
int a[maxn];
int l1,r1;
//int n,x,f;
int n;
void solve(int l,int r)
{
int x,f;
if(l>r)
return ;
cout<<"? "<<l<<" "<<r<<"\n";
cout.flush();
cin>>x>>f;
l1=r-f+1,r1=l+f-1;
if(l1<=r1)
{
rep(i,l1,r1+1)
a[i]=x;
solve(l,r-f);
solve(l+f,r);
}
else
{
solve(l,(l+r)>>1);
solve(((l+r)>>1)+1,r);
}
}
int main()
{
cin>>n;
// cout<<"? "<<1<<" "<<n<<"\n";
// cout.flush();
// cin>>x>>f;
solve(1,n);
cout<<"! ";
rep(i,1,n+1)
cout<<a[i]<<" ";
return 0;
}
//r-f+1 l+f-1 保底 x
//5 2
//2 2