拨箭寻古道的辙痕
华盖在暮色中鲸吞
当狼烟去云端一骑绝尘
普天下才唯我独尊
A
模拟
/* Author: 张皓南 Result: AC Submission_id: 2545167 Created at: Fri Apr 24 2020 19:07:11 GMT+0800 (China Standard Time) Problem_id: 3280 Time: 6 Memory: 1704 */
#include <stdio.h>
#include <string.h>
char zhn[50];
int len;
int main(){
scanf("%s",zhn+1);
len=strlen(zhn+1);
//printf("%d",len);
if(zhn[1]=='F') printf("19374299");
else if(zhn[1]=='S'){
if(zhn[3]=='o'){
printf("19376299");
}
else if(zhn[4]=='E'){
printf("19373299");
}
else if(zhn[4]=='J'){
printf("19375299");
}
}
else if(zhn[1]=='Z'){
if(zhn[4]=='Z'){
printf("19377299");
}
else if(zhn[4]=='X'){
printf("19379299");
}
}
return 0;
}
B
模拟
/* Author: 张皓南 Result: AC Submission_id: 2545369 Created at: Fri Apr 24 2020 19:10:53 GMT+0800 (China Standard Time) Problem_id: 3278 Time: 3 Memory: 1708 */
#include <stdio.h>
#include <string.h>
int m,n,i,j,x,y,s,t,tmp;
int zhn[50][50];
int main(){
scanf("%d%d",&m,&n);
for(i=1;i<=m;i++){
for(j=1;j<=n;j++){
scanf("%d",&zhn[i][j]);
}
}
while(scanf("%d%d%d%d",&x,&y,&s,&t)==4){
tmp=zhn[x][y];
zhn[x][y]=zhn[x+s][y+t];
zhn[x+s][y+t]=tmp;
}
for(i=1;i<=m;i++){
for(j=1;j<=n;j++){
printf("%d ",zhn[i][j]);
}
printf("\n");
}
return 0;
}
C
从头扫描A串,如果遇到B串的开头字母,那么往后查看从这个点开始,之后连着B的长度个字符,如果有不一样的就标记上,不输出;如果这lenb个字符和b全都一样,那么直接输出,然后把扫描的位置进行跳跃。
/* Author: 张皓南 Result: AC Submission_id: 2550985 Created at: Fri Apr 24 2020 21:32:03 GMT+0800 (China Standard Time) Problem_id: 3285 Time: 4 Memory: 1644 */
#include<stdio.h>
#include<string.h>
char a[50];
char b[50];
int i,j,flag,lena,lenb,k;
int main(){
gets(a);
gets(b);
lena=strlen(a);
lenb=strlen(b);
for(i=0;i<lena;){
int flag=0;
if(a[i]==b[0]&&i+lenb-1<lena){
//阔以
k=i;
for(j=0;j<lenb;j++,k++)if(a[k]!=b[j]) flag=1;
if(!flag){
printf("%d-%d\n",i,i+lenb-1);
i+=lenb;
}
else if(flag) i++;
}
else i++;
}
return 0;
}
D
天天就知道查日期,出题人也是挺无趣的
/* Author: 张皓南 Result: AC Submission_id: 2553096 Created at: Fri Apr 24 2020 23:46:21 GMT+0800 (China Standard Time) Problem_id: 3291 Time: 139 Memory: 1696 */
#include<stdio.h>
#include<string.h>
int y,m,r,i;
int yy,mm,rr,da,yu,d;
int mou[16]={
0,31,28,31,30,31,30,31,31,30,31,30,31};
int main(){
while(scanf("%d%d%d",&y,&m,&r)==3){
scanf("%d%d%d",&yy,&mm,&rr);
da=0;
d=0;
mou[2]=28;
if((yy%4==0&&yy%100!=0)||yy%400==0) mou[2]=29;
while(mm!=m||rr!=r){
rr++;
if(rr>mou[mm]){
mm++;
rr=1;
}
if(mm>12){
mm=1;
yy++;
if((yy%4==0&&yy%100!=0)||yy%400==0) mou[2]=29;
else mou[2]=28;
}
da++;
}
printf("%d\n",da);
}
return 0;
}
E
回文子串,马拉车算法安排
下篇博客可能会写一下,当复习了QWQ
/* Author: 张皓南 Result: AC Submission_id: 2547490 Created at: Fri Apr 24 2020 19:48:22 GMT+0800 (China Standard Time) Problem_id: 3325 Time: 2 Memory: 1736 */
#include<stdio.h>
#include<string.h>
#include<math.h>
char s[10000],s2[100000];
int p[10000];
int size,q,i,maxx;
void Manacher(char *s,int * p){
size=strlen(s);
p[0]=1;
int id=0;
int mx=1;
for(i=1;i<size;i++)
{
if(mx>i){
if(mx-i<p[2*id-i])
p[i]=mx-i;
else p[i]=p[2*id-i];
}
else p[i]=1;
for(;s[i+p[i]]==s[i-p[i]]&&(i-p[i]>=0);p[i]++);
if(mx<i+p[i]){
mx=i+p[i];
id=i;
}
}
}
int main(){
scanf("%d",&q);
while(q--){
maxx=0;
scanf("%s",s2);
size=strlen(s2);
for(i=0;i<2*size+1;i++){
s[i]='#';
s[++i]=s2[i/2];
}
Manacher(s,p);
for(i=0;i<size;i++) if(p[i]-1>maxx) maxx=p[i]-1;
printf("%d\n",maxx);
}
return 0;
}
F
不愧是水水的超越方程,确实是挺水的
/* Author: 张皓南 Result: AC Submission_id: 2548932 Created at: Fri Apr 24 2020 20:21:05 GMT+0800 (China Standard Time) Problem_id: 3319 Time: 142 Memory: 2864 */
#define lgr 2.71828182845
#include <stdio.h>
#include <math.h>
#include <string.h>
double a,b,c,mid;
int zhn(double x){
double ans=a*x*log(x)-b*pow(lgr,-pow(x-1/lgr,4))+c;
if(ans>0) return 1;
return -1;
}
int main(){
while(scanf("%lf%lf%lf",&a,&b,&c)!=EOF){
double l=1/lgr;
double r=1000000.00000;
int a=zhn(l);
int b=zhn(r);
if(a+b!=0){
printf("No solution.\n");
continue;
}
while(r-l>1e-6){
mid=(l+r)/2;
int c=zhn(mid);
if(c==a)l=mid;
else r=mid;
}
printf("%.8lf\n",mid);
}
return 0;
}
G
这题的排序其实挺令人头秃的,我记得杭电那个OJ有个类似的不过对称轴是随意的QWQ一开始我错了两次,我只考虑了把x排序,然后比较,但是有一种特殊情况把我hack了,那就是关于对称轴两边的点,x都相同,所以我们需要考虑一下纵坐标,纵坐标怎么搞呢我们先预处理出可能的答案(因为如果有答案那么一定是x坐标的最小值与最大值的平均值)
然后在这个对称轴左面的点按照y从大到小排序,对称轴右面的点从小到大进行排序
然后我们从左往右扫描,就可以先判断他对不对称,如果那个点位于对称轴上,那么就阔以停止QWQ
/* Author: 张皓南 Result: AC Submission_id: 2555674 Created at: Sat Apr 25 2020 12:30:43 GMT+0800 (China Standard Time) Problem_id: 3290 Time: 271 Memory: 9192 */
#include <stdio.h>
#include <math.h>
int n, anss, i;
double ans;
int flag;
struct point{
int x, y;
}zhn[500005];
int cmp(const void *a, const void *b){
if ((*(struct point *)a).x == (*(struct point *)b).x){
if ((*(struct point *)a).x > ans) return ((*(struct point *)a).y - (*(struct point *)b).y);
else return ((*(struct point*)b).y - (*(struct point *)a).y);
}
return ((*(struct point *)a).x-(*(struct point *)b).x);
}
int main(){
flag=1;
scanf("%d", &n);
int r=-2000000000, l=2000000000;
for (i=0;i<n;i++){
scanf("%d%d", &zhn[i].x, &zhn[i].y);
if (r<zhn[i].x) r=zhn[i].x;
if (l>zhn[i].x) l=zhn[i].x;
}
ans=((double)r+(double)l)/2.0;
qsort(zhn,n,sizeof(zhn[0]), cmp);
for (i=0;i<=(n+1)/2;i++){
if ((zhn[i].x<<1)==l+r)break;
if (zhn[i].x+zhn[n-1-i].x==l+r&&zhn[i].y==zhn[n-1-i].y) continue;
else{
flag = 0;
break;
}
}
if (flag) printf("x = %.1lf", ans);
else printf("Not a symmetric figure.");
return 0;
}
H
打表,不香吗
/* Author: 张皓南 Result: AC Submission_id: 2549697 Created at: Fri Apr 24 2020 20:37:32 GMT+0800 (China Standard Time) Problem_id: 3293 Time: 14 Memory: 1760 */
#include <stdio.h>
#include <math.h>
int zhn[10005]={
0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,........,};//质数表,一共是8715个好像
int l,r,mid,n,m;
int main(){
while(scanf("%d%d",&n,&m)==2){
l=0,r=8716;
while(l<r){
mid=(l+r)/2;
if(zhn[mid]==n) break;
else if(zhn[mid]>n)r=mid;
else if(zhn[mid]<n) l=mid+1;
}
//printf("shit%d",mid);
if(zhn[l]==n){
printf("%d\n",zhn[l+m]);
}
else if(zhn[r]==n){
printf("%d\n",zhn[r+m]);
}
else if(zhn[mid]==n){
printf("%d\n",zhn[mid+m]);
}
}
return 0;
}
I
这个题啊
首先根据数据范围,n^2 biss
,所以不能n^2,,这种1e5的应该考虑线性的或者带个log的
要求绝对值最大,我们先快排,
之后二分查找,ojbk
/* Author: 张皓南 Result: AC Submission_id: 2548432 Created at: Fri Apr 24 2020 20:09:30 GMT+0800 (China Standard Time) Problem_id: 3287 Time: 213 Memory: 1748 */
#include<stdio.h>
#include<string.h>
#include<math.h>
int n,k,i;
int arr[200005];
void swap(int *a, int *b){
int temp;
temp=*a;
*a=*b;
*b=temp;
}
void quickSort(int arr[] ,int start, int end){
int arrBase,arrMiddle;
int tempStart=start,tempEnd=end;
if(tempStart>=tempEnd) return;
arrBase=arr[start];
while(start<end){
while(start<end&&arr[end]>arrBase)end--;
if(start<end){
swap(&arr[start], &arr[end]);
start++;
}
while(start<end&&arr[start]<arrBase)
start++;
if(start<end){
swap(&arr[start], &arr[end]);
end--;
}
}
arr[start]=arrBase;
arrMiddle=start;
quickSort(arr,tempStart,arrMiddle-1);
quickSort(arr,arrMiddle+1,tempEnd);
}
int findd(int x){
//在这里找x
int flag=0;
int l=0,r=n+1;
int mid;
while(l<r){
mid=(l+r)/2;
if(arr[mid]==x) return 1;
else if(arr[mid]>x) r=mid;
else if(arr[mid]<x) l=mid+1;
}
if(arr[mid]==x||arr[l]==x||arr[r]==x) return 1;
else return 0;
}
int main(){
while(scanf("%d%d",&n,&k)==2){
for(i=1;i<=n;i++) scanf("%d",&arr[i]);
quickSort(arr,1,n);
for(i=1;i<=n;i++){
if(findd(k-arr[i])){
printf("%d %d\n",arr[i],k-arr[i]);
break;
}
}
}
return 0;
}
J
模拟
/* Author: 张皓南 Result: AC Submission_id: 2554240 Created at: Sat Apr 25 2020 09:08:56 GMT+0800 (China Standard Time) Problem_id: 3331 Time: 96 Memory: 1540 */
#define ll long long
#define modd 1000003
#include <stdio.h>
#include <math.h>
#include <string.h>
ll x1[10][10], x2[10][10],x4[10][10];
char a[10];
void zhn(){
memset(x4,0,sizeof(x4));
int i,j,k;
for(i=1;i<=7;i++){
for(j=1;j<=7;j++){
for(k=1;k<=7;k++){
x4[i][j]+=(x1[i][k]%modd*x2[k][j]%modd)%modd;
x4[i][j]=x4[i][j]%modd;
}
}
}
for(i= 1;i<=7;i++){
for(j=1;j<=7;j++){
x1[i][j]=x4[i][j];
}
}
}
int main(){
int i,j;
for(i=1;i<=7;i++) x1[i][i]=1;
while(gets(a)!=NULL){
for (i=1;i<=7;i++){
for (j=1;j<=7;j++){
x2[i][8-j]=(a[i-1]>>(j-1))&1;
}
}
zhn();
}
for(i=1;i<=7;i++){
for(j=1;j<=7;j++){
printf("%lld ",x1[i][j]);
}
printf("\n");
}
return 0;
}
K
wdnmD大模拟,没写
L
有更简单的做法,但是比较直观的就是写个大根堆
/* Author: 张皓南 Result: AC Submission_id: 2552952 Created at: Fri Apr 24 2020 23:34:21 GMT+0800 (China Standard Time) Problem_id: 3286 Time: 661 Memory: 7644 */
#include<stdio.h>
#include<string.h>
#include<math.h>
#define int long long
#define maxn 2000100
int ans;
int size,queue[maxn];
void shift_up(int i){
while(i>1)
{
if(queue[i]>queue[i>>1])
{
int temp=queue[i];
queue[i]=queue[i>>1];
queue[i>>1]=temp;
}
i>>=1;
}
}
void shift_down(int i){
while((i<<1)<=size)
{
int next=i<<1;
if(next<size && queue[next+1]>queue[next])
next++;
if(queue[i]<queue[next])
{
int temp=queue[i];
queue[i]=queue[next];
queue[next]=temp;
i=next;
}
else return ;
}
}
void push(int x){
queue[++size]=x;
shift_up(size);
}
void pop(){
int temp=queue[1];
queue[1]=queue[size];
queue[size]=temp;
size--;
shift_down(1);
}
int top(){
return queue[1];
}
main(){
int n,a,i,j,k;
scanf("%lld%lld",&n,&k);
for(i=1;i<=n;i++){
scanf("%lld",&a);
if(top()<=a&&k){
k--;
a=a/2;
push(a); //放入堆内
}
else if(top()>a&&k){
k--;
int tmp=top();
pop();
push(tmp/2);
push(a);
}
else if(!k) push(a);
}
for(i=1;i<=n;i++){
ans+=top();
pop(); //弹出堆顶元素
}
printf("%lld",ans);
return 0;
}