前言
第2題應該算普及難度的題了,但是比賽的時候漏看了一個條件導緻想不出來.
比賽總體來看應該是提高難度的.~~(事後諸葛亮)
正文
A A A
(1,1)為白即可.
int n,m,T;
char s[N][N];
int main() {
memset(s,'B',sizeof s);
qr(T); while(T--) {
qr(n); qr(m);
s[1][1]='W';
for(int i=1;i<=n;i++) {
s[i][m+1]=0;
puts(s[i]+1);
s[i][m+1]='B';
}
}
return 0;
}
B B B
a [ i ] + = a [ j ] ( j < i , 考 試 時 漏 看 了 Q A Q ) a[i]+=a[j](j<i,考試時漏看了QAQ) a[i]+=a[j](j<i,考試時漏看了QAQ).
直接從後往前掃,貪心即可.
int T,n,a[N],b[N],flag=1,s[3];
int main() { qr(T);
while(T--) {
qr(n); flag=1;
memset(s,0,sizeof s);
for(int i=1;i<=n;i++)
qr(a[i]),s[a[i]+1]++;
for(int i=1;i<=n;i++) qr(b[i]);
for(int i=n;i>=1;i--) {
int x=a[i];
s[x+1]--;
if(x==b[i]) continue;
if(x<b[i]) {
if(!s[2]) {flag=0; break;}
}
else {
if(!s[0]) {flag=0; break;}
}
}
if(!flag) puts("NO");
else puts("YES");
}
return 0;
}
C C C
考慮以每個位置結尾的合法開頭位置.
設目前結尾為 i i i,最前的合法開頭為 j j j.則有:
s [ ( j − 1 ) ∼ i ] 的 數 互 不 相 同 s[(j-1)\sim i]的數互不相同 s[(j−1)∼i]的數互不相同
設 m x = max j = 1 i l a s t p o s [ s [ j ] ] mx=\max_{j=1}^i lastpos[s[j]] mx=maxj=1ilastpos[s[j]].
則: s [ m x + 1 ∼ i ] s[mx+1\sim i] s[mx+1∼i]的數互不相同.
對應的最前的 j = m x + 2 , 對 答 案 的 貢 獻 為 i − j + 1 = i − ( m x + 2 ) + 1 = i − m x − 1 j=mx+2,對答案的貢獻為i-j+1=i-(mx+2)+1=i-mx-1 j=mx+2,對答案的貢獻為i−j+1=i−(mx+2)+1=i−mx−1
直接用map暴力一發即可.
int n,mx;
ll s[N],ans;
map<ll,int> h;
signed main() {
qr(n); mx=-1; h[0]=0;
for(int i=1;i<=n;i++) {
qr(s[i]); s[i]+=s[i-1];
if(h.count(s[i]))mx=max(mx,h[s[i]]);
h[s[i]]=i;
ans+=i-mx-1;
} pr2(ans);
return 0;
}
D D D
暴力計算所用的最少輪數 c n t cnt cnt和操作數 a n s ans ans.
由于經過一系列操作後一定不會回到原狀态,所有上界是有限的(正好為 a n s ans ans)
則 c n t ≤ k ≤ a n s cnt\le k\le ans cnt≤k≤ans時合法.
不然的話,暴力調整一下即可.
int n,m,cnt,ans,*f[N],_f[N*N],*Fpos=_f;
char s[N];
int main() {
qr(n),qr(m); if(m>n*n) {puts("-1");return 0;}
scanf("%s",s+1);
while(1) {
bool flag=0;
f[++cnt]=Fpos;
for(int i=1;i<n;i++)
if(s[i]=='R'&&s[i+1]=='L')
swap(s[i],s[i+1]),flag=1,(*++Fpos)=i++,ans++;
if(!flag) break;
}
--cnt;
if(!(cnt<=m&&m<=ans)) {puts("-1");return 0;}
int k=m-cnt;
for(int i=1;i<=cnt;i++) {
int t=f[i+1]-f[i];
if(k>=t-1) {
for(int *j=f[i]+1;j<=f[i+1];j++)
printf("1 %d\n",*j);
k-=t-1;
}
else {
int *j=f[i]+1;
while(k--) printf("1 %d\n",*j++);
pr1(f[i+1]-j+1);
while(j<=f[i+1]) pr1(*j++);
puts("");
k=0;
}
}
return 0;
}
E E E
/*
n<=2時顯然無解.
為了讓車的花費比皇後少.不妨引誘皇後倒數第二個數走到n*n-1,且不能走到n*n,同時讓車花費為0.
可以把n*n-1放在(1,1),n*n放在(2,n).對于行數>3的,讓它全掃完即可.
同時我們讓第二行倒數第二個走到放在第一列,第一列的數(除第一個位置遞增)即可.
*/
#include<map>
#include<set>
#include<queue>
#include<cmath>
#include<cstdio>
#include<vector>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#define lc (x<<1)
#define rc (x<<1|1)
#define gc getchar()//(p1==p2&&(p2=(p1=buf)+fread(buf,1,size,stdin),p1==p2)?EOF:*p1++)
#define mk make_pair
#define pi pair<int,int>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=510,size=1<<20;
//char buf[size],*p1=buf,*p2=buf;
template<class o> void qr(o &x) {
char c=gc; x=0; int f=1;
while(!isdigit(c)){if(c=='-')f=-1; c=gc;}
while(isdigit(c)) x=x*10+c-'0',c=gc;
x*=f;
}
template<class o> void qw(o x) {
if(x/10) qw(x/10);
putchar(x%10+'0');
}
template<class o> void pr1(o x) {
if(x<0)x=-x,putchar('-');
qw(x); putchar(' ');
}
template<class o> void pr2(o x) {
if(x<0)x=-x,putchar('-');
qw(x); puts("");
}
int m,n,a[N][N];
int main() {
qr(n); if(n<=2)return puts("-1"),0;
a[1][1]=n*n-1;
a[2][n]=n*n;
for(int i=n;i>1;i--)
for(int j=n; j;j--)
if(!a[i][j]) a[i][j]=++m;
for(int i=2;i<=n;i++) a[1][i]=++m;
swap(a[3][1],a[3][n-1]);
for(int i=1;i<=n;i++) {
for(int j=1;j<=n;j++) pr1(a[i][j]);
puts("");
}
return 0;
}
F F F
//思路來源:https://www.luogu.com.cn/blog/gyh20/post-1333f
//一個數出現的話,其約數一定也在集合内.
//是以gcd(a,b)也出現在集合内.
//答案即為最大的非自身約數.
//按非自身最大約數排序即可.
#include<map>
#include<set>
#include<queue>
#include<cmath>
#include<cstdio>
#include<vector>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#define lc (x<<1)
#define rc (x<<1|1)
#define gc getchar()//(p1==p2&&(p2=(p1=buf)+fread(buf,1,size,stdin),p1==p2)?EOF:*p1++)
#define mk make_pair
#define pi pair<int,int>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=5e5+10,size=1<<20;
//char buf[size],*p1=buf,*p2=buf;
template<class o> void qr(o &x) {
char c=gc; x=0; int f=1;
while(!isdigit(c)){if(c=='-')f=-1; c=gc;}
while(isdigit(c)) x=x*10+c-'0',c=gc;
x*=f;
}
template<class o> void qw(o x) {
if(x/10) qw(x/10);
putchar(x%10+'0');
}
template<class o> void pr1(o x) {
if(x<0)x=-x,putchar('-');
qw(x); putchar(' ');
}
template<class o> void pr2(o x) {
if(x<0)x=-x,putchar('-');
qw(x); puts("");
}
int n,f[N],ans[N];
bool cmp(int x,int y) {return f[x]<f[y];}
int main() {
f[1]=1; qr(n);
for(int i=1;i<=n;i++) for(int j=2*i;j<=n;j+=i) f[j]=i;
for(int i=1;i<=n;i++) ans[i]=i;
sort(ans+1,ans+n+1,cmp);
for(int i=2;i<=n;i++) pr1(f[ans[i]]);
return 0;
}
![iscc reverse[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)