10/02赛后总结

T1学习除法

题目传送门：学习除法http://bbcoj.cn/contest/1028/problem/1

说白了，就是检验是不是质数罢了，是质数输出0，不然输出1；

但是质数判断写错了

100分只有60分，damn

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
	freopen("divide.in","r",stdin);
	freopen("divide.out","w",stdout);
	int n,cnt;
	cin>>n;
	for(int i=2;i*i<=n;i++){
    //你猜我原来怎么写的：for(int i=1;i*i<=n;i++),服啦，还我40分
		if(n%i==0){
			cout<<1<<endl;
			return 0;
		}
	}
	cout<<0<<endl;
	return 0;
}

T2拆分

题目传送门：和积http://bbcoj.cn/contest/1027/problem/2

用的暴力枚举，但是没有记忆化，导致超时了，优化写的有误，最后只拿了50分

#include<bits/stdc++.h>
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma Gcc optinize("o1")
#pragma Gcc optinize("o2")
#pragma Gcc optinize("o3")
#pragma GCC optimize("Ofast")
using namespace std;
const int N=5e6+5;
int s[N],j[N];//记忆化
inline int read() {
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9') {
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9') {
		x=x*10+c-'0';
		c=getchar();
	}
	return x*f;
}
inline void add(int x) {
	int y=x;
	int sum=0,tmp=1;
	while(x) {
		sum+=x%10;
		tmp*=x%10;
		x/=10;
	}
	s[y]=sum;//记忆化
	j[y]=tmp;//记忆化
	return ;
}
int main() {
	freopen("sump.in","r",stdin);
	freopen("sump.out","w",stdout);
	int T;
	T=read();
	while(T--) {
		int m,n,k;
		m=read();
		n=read();
		k=read();
		int x=-2e9,ans=0;
		for(int i=m; i<=n; i++) {
			int sum,tmp;
			if(s[i]==0)add(i);//记忆化
			sum=s[i];
			tmp=j[i];
			if(sum==k&&tmp>x){
				x=tmp;
				ans=i;
			}	
		}
		printf("%d %d\n",ans,x);
	}
	return 0;
}

T3 部落

题目传送门：

部落http://bbcoj.cn/contest/1028/problem/3难得离谱,甚至比T4还难

#include<bits/stdc++.h>
using namespace std;
int n,m;
int cnt,ans;
int a[100005],s[100005];
inline int read() {
	int x=0;
	char c=getchar();
	while(c<'0'||c>'9')c=getchar();
	while(c>='0'&&c<='9') {
		x=(x<<3)+(x<<1)+c-'0';
		c=getchar();
	}
	return x;
}

int main(){
	freopen("town.in","r",stdin);
	freopen("town.out","w",stdout);
	n=read();
	m=read();
	for(int i=1;i<=n;i++) a[i]=read();
    s[++cnt]=a[1];
    for(int i=2;i<m;i++){
		if(s[cnt]<=a[i]) s[++cnt]=a[i];
        else{
			int num=lower_bound(s+1,s+cnt+1,a[i])-s;
            s[num]=a[i];
        }
    }
    if(s[cnt]<=a[m]) s[++cnt]=a[m];
    else{
		int num=lower_bound(s+1,s+cnt+1,a[m])-s;
        s[num]=a[m];
    }
    ans+=m-cnt;
    cnt=0;
	s[++cnt]=a[n];
    for(int i=n-1;i>m;i--){
		if(s[cnt]<=a[i]) s[++cnt]=a[i];
        else{
			int num=lower_bound(s+1,s+cnt+1,a[i])-s;
            s[num]=a[i];
        }
    }
    ans+=n-m-cnt;
    cout<<ans;
	return 0;
}

T4传递

传递

大模拟，结果以为是什么奇葩的算法，没写出来一点

#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int a[N],b[N],n,m,k,q;
int ans,s,t;
inline int read() {
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') {
		if(ch=='-') w=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9') {
		s=s*10+ch-'0';
		ch=getchar();
	}
	return s*w;
}
int main() {
	freopen("spread.in","r",stdin);
	freopen("spread.out","w",stdout);
	n=read();
	m=read();
	k=read();
	q=read();
	for(int i=1; i<=n; i++) a[i]=read();
	for(int i=1; i<=n; i++) b[i]=read();
	int tmp=1;
	while(true) {
		if(s>=n&&t>=n){
			cout<<ans;
			return 0;
		}
		if(tmp==1) {
			if(q>=abs(a[s+1]-b[t])&&s<n)	s++;
			else if(b[t+1]-b[t]<=m&&t<n)	t++;
			else if(b[t+1]-b[t]>m&&q>=abs(a[s]-b[t])&&t<n){
				tmp=2;
				ans++;
				continue;
			} else 	s++;
		} else {
			if(q>=abs(b[t+1]-a[s])&&t<n)	t++;
			else if(a[s+1]-a[s]<=m&&s<n)	s++;
			else if(a[s+1]-a[s]>m&&q>=abs(b[t]-a[s])&&s<n) {
				ans++; 
				tmp=1;
				continue;
			} else	t++;
		}
	}
	return 0;
}