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;
}