csp-j 複賽感想
作者：部落格園小蔡編程
這次是作者第一次參加csp-j的比賽
內心還是挺激動的
今天，作者就來和大家討論一下這次csp-j的學習心得和感想
T1 分糖果
這題描述看似複雜
其實就是一道求最大取模的題
L<=k<=R
求k%n的最大值
有多種方法
作者這裡目測100
#include <cstdio>
#define ll long long
ll n,l,r;
int main(){
freopen("candy.in","r",stdin);
freopen("candy.out","w",stdout);
scanf("%lld%lld%lld",&n,&l,&r);
ll m=l%n;
m=n-m-1;
if(l+m>r) printf("%lld",r%n);
else printf("%lld",n-1);
return 0;
}
T2 插入排序
著道題是經典的模擬
只要把插入排序換成二分就行了
但是作者比賽時為了更多的分數
先做後面的題，成功獲得了大約120分
這題只拿了一半的分數
#include<bits/stdc++.h>
using namespace std;
const int N=8e3+10;
int n,q;
struct node{
int n,d;
} a[N];
int p,v,u;
int cr(int g){
node x[N];
for(int i=1;i<=n;i++){
x[i].n=i;
x[i].d=a[i].d;
}
for (int i = 1; i <= n; i++)
for (int j = i; j>=2; j--)
if ( x[j].d < x[j-1].d ){
int t=x[j].d;
int f=x[j].n;
x[j].d=x[j-1].d;
x[j].n=x[j-1].n;
x[j-1].d=t;
x[j-1].n=f;
}
int res;
for(int i=1;i<=n;i++)
if(x[i].n==g) {
res=i;
break;
}
return res;
}
int main(){
freopen("sort.in","r",stdin);
freopen("sort.out","w",stdout);
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++) scanf("%d",&a[i].d),a[i].n=i;
for(int i=1;i<=q;i++){
scanf("%d",&p);
if(p==1){
scanf("%d%d",&v,&u);
a[v].d=u;
}else{
scanf("%d",&v);
printf("%d\n",cr(v));
}
}
//for(int i=1;i<=n;i++) printf("%d ",a[i].d);
return 0;
}
T3 網路連接
這題的數據量很弱，n<=1000，不會超時
但是這題的關鍵點在於判斷IP是否正確
需要寫很麻煩的if語句
比如說：10:2.3.1.2 （這IP作者一開始就沒考慮到）
所以目測65分
#include <bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int n;
string op,ad;
int a,b,c,d,e;
int da[N][7],dal;
int sop(string x){
int res[10],l=1;
int v=0;
for(int i=0;i<x.size();i++){
if(x[i]=='.'&&l<4) res[l++]=i;
else if(x[i]=='.'&&l==4) v=1;
else if(x[i]==':'&&l==4) res[l++]=i;
else if(x[i]==':'&&l!=4) v=1;
}
if(v) return 0;
a=0;
b=0;
c=0;
d=0;
e=0;
for(int i=0;i<res[1];i++){
a=a*10+int(x[i])-48;
if(a==0&&i==1) v=1;
}
for(int i=res[1]+1;i<res[2];i++){
b=b*10+int(x[i])-48;
if(b==0&&i==1) v=1;
}
for(int i=res[2]+1;i<res[3];i++){
c=c*10+int(x[i])-48;
if(c==0&&i==1) v=1;
}
for(int i=res[3]+1;i<res[4];i++){
d=d*10+int(x[i])-48;
if(d==0&&i==1) v=1;
}
for(int i=res[4]+1;i<x.size();i++){
e=e*10+int(x[i])-48;
if(e==0&&i==1) v=1;
}
if(a>255) v=1;
if(b>255) v=1;
if(c>255) v=1;
if(d>255) v=1;
if(e>65535) v=1;
if(v) return 0;
return 1;
}
int sad(){
int v=0;
for(int i=0;i<dal;i++){
if(a==da[i][0]&&b==da[i][1]&&c==da[i][2]&&d==da[i][3]&&e==da[i][4]) {
v=i+1;
break;
}
}
if(v) return v;
return 0;
}
int main(){
freopen("network.in","r",stdin);
freopen("network.out","w",stdout);
cin >> n;
for(int i=1;i<=n;i++){
cin >> op >> ad;
if(op=="Server"){
if(sop(ad)){
if(sad()==0){
da[dal][0]=a;
da[dal][1]=b;
da[dal][2]=c;
da[dal][3]=d;
da[dal][4]=e;
da[dal++][5]=i;
cout << "OK" << endl;
}
else{
cout << "FAIL" << endl;
}
}
else{
cout << "ERR" << endl;
}
}else{
if(sop(ad)){
int sadn=sad();
if(sadn){
cout << da[sadn-1][5] << endl;
}
else{
cout << "FAIL" << endl;
}
}
else{
cout << "ERR" << endl;
}
}
}
return 0;
}
T4 小熊的果籃
隨便說一句：為什麼去年和今年T4的主人公都是小熊？
這道題的關鍵點在讀題
塊有可能合併
所以要不斷重新掃描塊
作者用了前綴和來計算塊
目測70分
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n,m;
int a[N],c[N],g[N],b[N],k[N];
int main(){
freopen("fruit.in","r",stdin);
freopen("fruit.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
while(n>m){
int l=1;
for(int i=1;i<=n;i++){
if(g[i]==0) {
b[l++]=a[i];
k[l-1]=i;
}
}
for(int i=1;i<l;i++){
c[i]=1;
if(b[i]==b[i-1]&&i>1)c[i]=c[i-1]+1;
}
int v=0;
for(int i=1;i<l;i++){
if(c[i]==1) {
if(v) printf(" ");
v=1;
printf("%d",k[i]);
m++;
g[k[i]]=1;
}
}
printf("\n");
}
return 0;
}
感想
這次csp-j的數據都很良心
作者暴力枚舉也能得很多分
而讀題尤其重要
T3 IP的判斷正誤 和 T4 塊的合併
不要考試時糾結一道題
可以先把所有題暴力做一遍，拿到分數，再優化
現在洛谷民間數據100+52+65+70
希望這次csp大家能考出好成績
