M：A+B
臨時加的簽簽到到題
L：數學
代進去求一下，簽到題
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
int v;
int main(){
puts("217341");
return 0;
} H：書
簽到題，
注意到如果是全相同的字母的串，比如aaaaa，只能全刪
否則出現了兩種字母，如abba，abcba，ddz
如果不是回文串，顯然不用刪；
否則，把最后一個字母刪掉即可
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
int T;
char s[205];
int cal(){
bool sm=1;
int n=strlen(s);
for(int i=1;i<n;++i){
sm&=(s[i]==s[i-1]);
}
if(sm)return n;
for(int i=0;i<n;++i){
if(s[i]!=s[n-1-i]){
return 0;
}
}
return 1;
}
int main(){
scanf("%d",&T);
while(T--){
scanf("%s",s);
printf("%d\n",cal());
}
return 0;
} A： Lucky Number その１
簽到題，對區間內每個數暴力統計即可
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int N=5e5+10;
int t,n,k,x,y;
int cal(int x){
int c=0;
for(;x;x/=10){
if(x%10==4)c++;
else{
if(c==1 || c==2)return 0;
c=0;
}
}
if(c==1 || c==2)return 0;
return 1;
}
int main(){
while(~scanf("%d%d",&x,&y)){
if(x==-1 && y==-1)break;
t++;
assert(0<=x && x<=y && y<=100000);
int ans=0;
for(int i=x;i<=y;++i){
ans+=cal(i);
}
printf("%d\n",ans);
}
assert(t<=6);
return 0;
} E： 完美陣列
分類討論，貪心，遵循兩條原則，
1.前面盡量正負交替，開頭的值用多的那個
2.在前面能不用零盡量不用零，零可以放在任意位置，還能block兩個同符號的值
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int t,n,v,zero,ans[N];
vector<int>z,f;
bool solve(){
int c=0;
for(int i=1;i<=n;++i){
if(c>=1){
if(ans[c]>0){
if(f.size()){
int v=f.back();f.pop_back();
ans[++c]=v;
}
else if(zero){
zero--;
ans[++c]=0;
}
else{
return 0;
}
}
else if(ans[c]<0){
if(z.size()){
int v=z.back();z.pop_back();
ans[++c]=v;
}
else if(zero){
zero--;
ans[++c]=0;
}
else{
return 0;
}
}
else{
if(!z.size() && !f.size()){
zero--;
ans[++c]=0;
}
else if(z.size()>f.size()){
int v=z.back();z.pop_back();
ans[++c]=v;
}
else{
int v=f.back();f.pop_back();
ans[++c]=v;
}
}
}
else{
if(!z.size() && !f.size()){
zero--;
ans[++c]=0;
}
else if(z.size()>f.size()){
int v=z.back();z.pop_back();
ans[++c]=v;
}
else{
int v=f.back();f.pop_back();
ans[++c]=v;
}
}
}
return 1;
}
int main(){
scanf("%d",&t);
while(t--){
scanf("%d",&n);
zero=0;z.clear();f.clear();
for(int i=1;i<=n;++i){
scanf("%d",&v);
if(v==0)zero++;
else if(v<0)f.push_back(v);
else z.push_back(v);
}
if(!solve())puts("NO");
else{
puts("YES");
for(int i=1;i<=n;++i){
printf("%d ",ans[i]);
}
puts("");
}
}
return 0;
} G：積木
我：第一簽到題
夏老師：真的嗎真的嗎真的嗎
預期的簽到題，但好像不太符合預期
可能是因為大家不一定打過icpc昆明/徐州
注意到一個事實，如果[1,i]的和大于等于i+1，則它們也能湊出[1,i+1]的和
所以，k<=2的時候答案為k，否則能不斷吞并，為sum-k+1
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
int T,n,k;
int main(){
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&k);
if(k<=2)printf("%d\n",k);
else printf("%lld\n",1ll*n*(n+1)/2-k+1);
}
return 0;
} C: 高空走鋼索
在只有一個人或兩個人的時候，一趟即可，
考慮四個人的情形，在有1 2 3 4四個人（認為1時間最短4時間最長）的時候，
要么是12先過去，1回，34再過去，2回，然后只剩12，
要么是14先過去，1回，13再過去，1回，然后只剩12
i個人規模遞回到i-2個人規模，所以做個dp即可
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e3+10;
int t,n,a[N];
ll dp[N];
int main(){
scanf("%d",&t);
assert(t<=100);
while(t--){
scanf("%d",&n);
assert(n<=1000);
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
assert(a[i]<=100000);
}
sort(a+1,a+n+1);
dp[1]=a[1];dp[2]=a[2];
for(int i=3;i<=n;++i){
dp[i]=min(dp[i-1]+a[i]+a[1],dp[i-2]+a[2]+a[1]+a[i]+a[2]);
}
printf("%lld\n",dp[n]);
//assert(dp[n]<=1ll<<32);
}
return 0;
} B: Lucky Number その２
注意到范圍1e18，所以只能數位dp
可能大家的做法都不太一樣，驗題人的做法是，
直接做不太好做，所以考慮用總的減掉不合法的方案數，
所以，需要統計出現了長度為1的4或長度為2的4的方案，
dp[i][j][0/1]表示當前在第i位連續遇到了j個4是否已經出現了一段長度為1的4或者一段長度為2的4的方案數
然后數位dp套套模板，列舉下這位填幾，會不會給連續的4產生影響，有沒有出現一段長為1的4或者長為2的4
真的猛士，敢于先寫B后寫A
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int N=5e5+10;
ll x,y,a[20],dp[20][20][2];
ll dfs(int x,int four,bool has,bool up){
//printf("x:%d four:%d has:%1d up:%1d\n",x,four,has,up);
if(x==0){
return has==1 || four==1 || four==2;
}
if(!up && ~dp[x][four][has]){
return dp[x][four][has];
}
ll ans=0;
int lim=up?a[x]:9;
for(int i=0;i<=lim;++i){
if(four==1 || four==2){
if(i==4){
ans+=dfs(x-1,four+1,has,up && i==lim);
}
else{
ans+=dfs(x-1,0,1,up && i==lim);
}
}
else{
if(i==4){
ans+=dfs(x-1,four+1,has,up && i==lim);
}
else{
ans+=dfs(x-1,0,has,up && i==lim);
}
}
}
if(!up)dp[x][four][has]=ans;
//printf("x:%lld four:%lld has:%lld dp:%lld\n",x,four,has,dp[x][four][has]);
return ans;
}
ll cal(ll x){
if(x<=0)return 0;
int c=0;
for(;x;x/=10){
a[++c]=x%10;
}
memset(dp,-1,sizeof dp);
return dfs(c,0,0,1);
}
int main(){
while(~scanf("%lld%lld",&x,&y)){
if(x==-1 && y==-1)break;
ll n=y-x+1,ill=cal(y)-cal(x-1);
//printf("n:%lld ill:%lld",n,ill);
printf("%lld\n",n-ill);
}
return 0;
} J：貓
出題人：你看看這個題
我：你這不是原題，hdu6187
出題人：不是啊，是日本icpc2010的題
于是出題人沒有改悔，可能下次還會再犯
考慮拆掉的最小，于是保留的最大，
保留的部分是沒有環的，所以是求個最大生成樹
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int N=1e4+10,M=3e4+10;
int n,m;
int par[N];
P a[N];
double sum,ans;
int find(int x){
return par[x]==x?x:par[x]=find(par[x]);
}
struct node{
int u,v;
double w;
}e[M];
bool operator<(node a,node b){
return a.w>b.w;
};
double sq(double x){
return x*x;
}
double cal(P a,P b){
return sqrt(sq(a.first-b.first)+sq(a.second-b.second));
}
int main(){
scanf("%d%d",&n,&m);
//if(n==10000)while(1);
assert(1<=n && n<=10000);
assert(1<=m && m<=30000);
for(int i=1;i<=n;++i){
par[i]=i;
scanf("%d%d",&a[i].first,&a[i].second);
assert(-10000<=a[i].first && a[i].first<=10000);
assert(-10000<=a[i].second && a[i].second<=10000);
}
for(int i=1;i<=m;++i){
scanf("%d%d",&e[i].u,&e[i].v);
assert(1<=e[i].u && e[i].u<=n);
assert(1<=e[i].v && e[i].v<=n);
assert(e[i].u!=e[i].v);
e[i].w=cal(a[e[i].u],a[e[i].v]);
}
sort(e+1,e+m+1);
for(int i=1;i<=m;++i){
int u=find(e[i].u),v=find(e[i].v);
sum+=e[i].w;
if(u==v)continue;
par[v]=u;ans+=e[i].w;
}
printf("%.10lf\n",sum-ans);
return 0;
} K：畫
先假設所有都自己完成，然后考慮哪些能翻轉，
考慮第i天抄了第j次，則(i-1)-(j-1)次自己完成，最后獲得(2*(j-1)-(i-1)+P)*Q的收益，
相比自己完成，額外收益是(2*(j-1)-(i-1)+P)*Q-c[i]=2*(j-1)*Q+P*Q-(i-1)*Q-c[i]
注意到i、j分離之后，可以分別統計貢獻，
考慮列舉一共抄了j次，則2*(j-1)*Q的和固定，
只需求前j大的-(i-1)*Q-c[i]，這個排序一下即可
被出題人教育了，才得出來的做法，
我一開始的做法是先都抄，然后倒著dp[i]維護后綴抄了i天的最大收益
抄作業不快樂么
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int N=5e5+10;
int n,p,q,c[N],id[N];
ll ans,tmp;
bool cmp(int x,int y){
return 1ll*(x-1)*p+c[x]<1ll*(y-1)*p+c[y];
}
int main(){
scanf("%d%d%d",&n,&p,&q);
assert(1<=n && n<=500000);
assert(0<=p && p<=500000);
assert(abs(q)<=500000);
for(int i=1;i<=n;++i){
scanf("%d",&c[i]);
assert(abs(c[i])<=500000);
tmp+=c[i];
id[i]=i;
}
sort(id+1,id+n+1,cmp);
ans=tmp;
for(int j=1;j<=n;++j){
tmp-=1ll*(id[j]-1)*p+c[id[j]];
tmp+=2ll*(j-1)*p+1ll*p*q;
ans=max(ans,tmp);
}
printf("%lld\n",ans);
return 0;
} F: 完美數對
據說是微信的面試題，巧妙構造，
但是我不會，充分體現了沒有腦子，
賽后：好耶，大家也沒有腦子
首先注意到k>C(n,2)一定沒解，否則一定有解，
如果，我們能找到2*i是完全平方數，2*j是完全平方數，i+j是完全平方數
則總共放了x個i、j，x個點內部是一個團（兩兩有邊），貢獻是x*(x-1)/2
這里采取打表的方式，找到了一組(i,j)=(2,98)，
找到滿足x*(x-1)/2<=k的最大x，然后還剩k-x*(x-1)/2條邊
如果k-x*(x-1)/2=0，就隨便放不會影響答案的值即可，
否則，欽定一個和2能連邊的值，由此確定了2的個數
此時，如果還有多余的，隨便放不會影響答案的值即可
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int N=5e5+10;
int t,n,k,x,y;
int main(){
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&k);
if(k>n*(n-1)/2){
puts("No");
continue;
}
puts("Yes");
for(x=0;x*(x-1)/2<=k;++x);x--;
y=k-x*(x-1)/2;
if(!y){
for(int i=1;i<=x;++i){
printf("%d ",2);
}
for(int i=1;i<=n-x;++i){
printf("%d ",3);
}
}
else{
for(int i=1;i<=y;++i)printf("%d ",2);
for(int i=1;i<=x-y;++i)printf("%d ",98);
printf("%d ",223);
for(int i=1;i<=n-x-1;++i)printf("%d ",1);
}
puts("");
}
return 0;
} D: 正方形數數
驗題人是O(n^2logn)亂搞過的，我永遠喜歡資料結構.jpg
官方題解有O(n^2)的做法，我不聽我不聽我不聽
樣例給了啟發，
首先l、r、u、d分別維護左右上下相同的能擴展的長度，
然后考慮怎么統計答案，這里是列舉對角線從左上到右下，
考慮B點維護一個向左向上的殼，A點插入一個向右向下的殼，
如果A能覆寫到B且B能覆寫到A，且AB值相同就是一個合法的正方形，
所以考慮每條對角線的平行線，開一個樹狀陣列
同一條線上的所有排序，第一關鍵字是值，第二關鍵字是位置，
對所有相同的值尺取，先插入再統計答案，然后撤銷掉
記A的位置是同一條線上的pos，向右下cover的范圍是[pos,pos+v-1]（線段1）
其中，v是向右向下二者的短邊的長度，
則B的位置是pos2，向左上cover的范圍是[pos2-w+1,pos2]（線段2）
其中，w是向左向上二者的短邊的長度，
A、B構成一個合法的正方形當且僅當線段1覆寫住pos2且線段2覆寫住pos1
這是一個經典問題，這里的做法是，
先把A在pos點插入，在pos+v點撤銷（這里用了一個優先佇列）
然后B經過的時候，統計區間內值的方案數即可
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
const int N=1e3+10,M=2e3+5,off=1e3;
int tr[M][N],l[N][N],r[N][N],u[N][N],d[N][N];
int n,m,a[N][N],ans;
priority_queue<P,vector<P>,greater<P> >q;
void add(int id,int x,int v){
for(int i=x;i<N;i+=i&-i){
tr[id][i]+=v;
}
}
int sum(int id,int x){
if(x<=0)return 0;
int ans=0;
for(int i=x;i>0;i-=i&-i){
ans+=tr[id][i];
}
return ans;
}
struct node{
int id,x,y,v;
}e[N];
bool cmp(node a,node b){
return a.v<b.v || (a.v==b.v && a.id<b.id);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
scanf("%d",&a[i][j]);
l[i][j]=(a[i][j]==a[i][j-1]?l[i][j-1]+1:1);
u[i][j]=(a[i][j]==a[i-1][j]?u[i-1][j]+1:1);
}
}
for(int i=n;i>=1;--i){
for(int j=m;j>=1;--j){
r[i][j]=(a[i][j]==a[i][j+1]?r[i][j+1]+1:1);
d[i][j]=(a[i][j]==a[i+1][j]?d[i+1][j]+1:1);
}
}
for(int dig=1-n;dig<=m-1;++dig){
int i,j,c=0,id=dig+off;
if(dig<=0)j=1,i=j-dig;
else i=1,j=i+dig;
for(;i<=n&&j<=m;++i,++j){
++c;
e[c]={c,i,j,a[i][j]};
}
sort(e+1,e+c+1,cmp);
for(int x=1;x<=c;){
int y=x;
while(y+1<=c && e[y+1].v==e[x].v){
y++;
}
for(int z=x;z<=y;++z){
i=e[z].x,j=e[z].y;
int pos=min(i,j);
int w=min(l[i][j],u[i][j]);
int v=min(r[i][j],d[i][j]);
while(!q.empty() && q.top().first<=pos){
int r=q.top().second;q.pop();
add(id,r,-1);
}
add(id,pos,1);
//printf("a:%d b:%d\n",sum(id,pos),sum(id,pos-w));
q.push(P(pos+v,pos));
int more=sum(id,pos)-sum(id,pos-w);
//printf("w:%d\n",w);
ans+=more;
//printf("i:%d j:%d more:%d\n",i,j,more);
}
while(!q.empty()){
int r=q.top().second;q.pop();
add(id,r,-1);
}
x=y+1;
}
}
printf("%d\n",ans);
return 0;
}I: 棋
驗題人不會，給的定位是防AK題，可以參考官方題解
大概思路是，先把曼哈頓距離轉成切比雪夫距離
然后考慮維護一個四維dp，
dp[i][j][k][l]控制xmin,xmax,ymin,ymax，
每次加入一行或一列統計貢獻
驗題人的貢獻及吐槽
修復了完美陣列spj的bug，
修復了完美陣列的樣例數，書的字符長度的bug
亂搞了若干暴力做法、假做法沒有艸過去，
構造造了個越界的也沒有艸過去，
好家伙，全都防住了啊，那就是沒鍋了
個人認為，出題人出了一套好題，沒有模板題，好評好評~
主校區與軟院負責參與策劃、布置、監考、出題、驗題的同學們都辛苦了~
參賽的同學們也辛苦了~
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/277758.html
標籤：其他