回文
一句话题意：从左上角到右下角的路径上的字母能组成回文串的路径有几条
题解
暴力做法是从左上角和右下角分别往对方 \(dp\)，复杂度为 \(\mathcal O(n^4)\)
因为状态只有在 \(x1+x2+y1+y2 = n+m+2\) 时合法，
则确定三个变量即可推出剩下一个变量，
复杂度为 \(\mathcal O(n^3)\)
#include<bits/stdc++.h>
#define ll long long
#define N 510
#define mod 993244853
using namespace std;
int n,m,a[N][N],f[N][N][N];
int main(){
freopen("palin.in","r",stdin);
freopen("palin.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i = 1;i<=n;i++){
string s;
cin>>s;
for(int j = 1;j<=m;j++)
a[i][j] = s[j-1]-'a';
}
int mid = (n+m)>>1;
f[1][1][n] = a[1][1]==a[n][m];
for(int i = 1;i<=mid;i++){
for(int x1 = max(1,i-m+1);x1<=min(i,n);x1++){
int y1 = i-x1+1;
for(int x2 = max(1,n-i+1);x2<=min(n,n+m-i);x2++){
int y2 = n+m+1-i-x2;
if(a[x1][y1+1]==a[x2][y2-1])
f[i+1][x1][x2] = (ll)(f[i+1][x1][x2]+f[i][x1][x2])%mod;
if(a[x1][y1+1]==a[x2-1][y2])
f[i+1][x1][x2-1] = (ll)(f[i+1][x1][x2-1]+f[i][x1][x2])%mod;
if(a[x1+1][y1]==a[x2][y2-1])
f[i+1][x1+1][x2] = (ll)(f[i+1][x1+1][x2]+f[i][x1][x2])%mod;
if(a[x1+1][y1]==a[x2-1][y2])
f[i+1][x1+1][x2-1] = (ll)(f[i+1][x1+1][x2-1]+f[i][x1][x2])%mod;
}
}
}
ll ans = 0;
if((n+m)&1){
for(int i = max(1,mid-m+1);i<=min(n,mid);i++){
int j = mid-i+1;
if(i<n) ans = (ll)(ans+f[mid][i][i+1])%mod;
if(j<m) ans = (ll)(ans+f[mid][i][i])%mod;
}
}else{
for(int i = max(1,mid-m+1);i<=min(n,mid);i++)
ans = (ll)(ans+f[mid][i][i])=%mod;
}
printf("%lld",ans);
return 0;
}
快速排序
一句话题意：自己看去
题解
对于所有数字来说一定是升序的
再考虑对于 \(nan\) 来说该怎么排序
以从头确定每一个位置的思路来考虑，
对于 \(x_i\) 来说，他前面是确定的，只用考虑它和它后面该如何排序，
对于非 \(nan\) 的情况，显然，它会将所有小于它的数排在它前面，并将自己确定在中间，
对于是 \(nan\) 的情况，显然，它会将自己置于原地并继续往后走
以此递归考虑
#include<bits/stdc++.h>
#define N 500010
using namespace std;
int T,n,cnt,bs,bl,a[N],b[N],c[N];
int main(){
freopen("qsort.in","r",stdin);
freopen("qsort.out","w",stdout);
scanf("%d",&T);
while(T--){
bs = 0;bl = 1;cnt = 0;
scanf("%d",&n);
for(int i = 1;i<=n;i++){
char s[12];
scanf("%s",s);
if(*s!='n'){
sscanf(s,"%d",a+i);
b[++bs] = a[i];
}else a[i] = -1;
}
sort(b+1,b+bs+1);
b[bs+1] = 0x3f3f3f3f;
for(int i = 1;i<=n;i++){
if(a[i]==-1) c[++cnt] = -1;
else{
if(b[bl]>a[i]) continue;
while(b[bl]<a[i]) c[++cnt] = b[bl++];
c[++cnt] = b[bl++];
}
}
for(int i = 1;i<=n;i++){
if(~c[i]) printf("%d ",c[i]);
else printf("nan ");
}
puts("");
}
return 0;
}
混乱邪恶
题解
模拟退火可以秒掉，也就交了几页
#include<bits/stdc++.h>
#define N 1000010
using namespace std;
const double tp = 0.9999999;
mt19937 rnd(time(0));
struct node{
int val,id,c;
}a[N];
int n,m;
long long sum,tot;
bool cmp_val(node a,node b){
return a.val<b.val;
}
bool cmp_id(node a,node b){
return a.id<b.id;
}
void output(){
puts("NP-Hard solved");
sort(a+1,a+n+1,cmp_id);
for(int i = 1;i<=n;i++){
if(a[i].c==1) printf("1 ");
else printf("-1 ");
}
exit(0);
}
void solve(){
double T = 5555560;
while(T>=1e-15){
int st = abs(tot-sum);
int w = rnd()%n+1;
if(a[w].c==1) a[w].c = -1,tot-=a[w].val;
else a[w].c = 1,tot+=a[w].val;
int ed = abs(tot-sum);
if(st<ed&&rnd()*1.0/429496726.114>exp((st-ed)/T)){
if(a[w].c==1) a[w].c = -1,tot-=a[w].val;
else a[w].c = 1,tot+=a[w].val;
}
if(tot==sum) output();
T*=tp;
}
}
int main(){
freopen("chaoticevil.in","r",stdin);
freopen("chaoticevil.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i = 1;i<=n;i++){
scanf("%d",&a[i].val);
a[i].id = i;
sum+=a[i].val;
}
if(sum&1) puts("Chaotic evil");
else{
sum/=2;
sort(a+1,a+n+1,cmp_val);
for(int i = n;i>=1;i--){
if(tot<sum) a[i].c = 1,tot+=a[i].val;
else a[i].c = -1;
}
if(tot==sum) output();
solve();
puts("Chaotic evil");
}
return 0;
}
接下来说正解
不妨设 \(n\) 为偶数，若 \(n\) 为奇数，我们考虑加入一个 \(a_n+1 = 0\)，归约到偶数的情况
我们将 \(a\) 排序，并构造 \(d_i = a_{2i} − a_{2i}−1\) 可以发现 \(\sum d_i ≤ m − \frac n 2 < n\)
我们尝试对于每个 \(d_i\) 分配一个 \(e_i\) 使得 \(\sum d_ie_i = 0\)，这样便可以构造出一组满足条件的 \(c_i\)。
我们不难归纳得出，若 \(n\) 个正整数 \(d_1, d_2,\cdots,d_n\) 的和为偶数且小于 \(2n\)，
则必存在一种方案： \(n = 1\) 显然成立。 对于 \(n = k\) ，若 \(d_i = 1\) 显然成立。
若存在 \(d_i > 1\) 我们考虑将 d 的最大值 \(\max \ d\) 和最小值 \(\min \ d\) 删除，并加入 \(\max \ d − \min \ d\)。
不难发现总和减少了 \(2 \min \ d\) 即至少 \(2\)，且最小值仍然非零，问题归约到 \(n ′ = n − 1\) 的情况
因此我们证明了一定存在合法的构造方案，并能成功给出一种构造。 复杂度 \(\mathcal O(n log^2 n)\)。
#include<bits/stdc++.h>
#define N 1000010
using namespace std;
int n,m,tot,a[N],ls[N],rs[N],rnk[N],v[N],c[N];
bool vis[N];
class cmp1{public:inline bool operator()(int x,int y){return v[x]>v[y];}};
class cmp2{public:inline bool operator()(int x,int y){return v[x]<v[y];}};
priority_queue<int,vector<int>,cmp1>q1;
priority_queue<int,vector<int>,cmp2>q2;
void dfs(int p,int x){
if(p<=0){
c[-p] = x;
return ;
}
dfs(ls[p],-x);
dfs(rs[p],x);
}
void solve(){
for(int i = 1;i<=tot;i++) q1.push(i),q2.push(i);
while(true){
int t = q2.top();q2.pop();
while(vis[t]){
t = q2.top();
q2.pop();
}
if(v[t]==1){
int x = 1;
for(int i = 1;i<=tot;i++){
if(!vis[i]){
dfs(i,x);
x = -x;
}
}
return ;
}
int s = q1.top();q1.pop();
while(vis[s]){
s = q1.top();
q1.pop();
}
vis[s] = vis[t] = 1;
v[++tot] = v[t]-v[s];
ls[tot] = s;rs[tot] = t;
q1.push(tot);q2.push(tot);
}
}
int main(){
freopen("chaoticevil.in","r",stdin);
freopen("chaoticevil.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i = 1;i<=n;i++){
scanf("%d",&a[i]);
rnk[i] = i;
}
sort(rnk+1,rnk+n+1,[](int x,int y){
return a[x]<a[y];
});
for(int i = n;i>0;i-=2){
ls[++tot] = -rnk[i-1];
rs[tot] = -rnk[i];
v[tot] = a[rnk[i]]-a[rnk[i-1]];
}
solve();
puts("NP-Hard solved");
for(int i = 1;i<=n;i++)
printf("%d ",c[i]);
puts("");
return 0;
}
第四题因为我是傻逼做不来就鸽了吧
标签：校内,val,int,sum,tot,freopen,230729,define From： https://www.cnblogs.com/cztq/p/17728738.html