img

mansoup

Java/Algorithm

汤哲鑫

个人站

欢迎来到我的个人站~

ecnu2

| 阅读：次

2. ECNU水题-2

1.找数

//超时我的程序，给我思路，一般大于int的数不要设计计算，否则很慢
#include<bits/stdc++.h>
using namespace std;

bool isUpNum(long long num) {
	stack<int> s;
	while(num>0){
		int n;
		n=num%10;
		num/=10;
		if(s.empty()){
			s.push(n);
		}else if(s.top()>n){
			return false;
		}else if(s.top()<=n){
			s.push(n);
		}
	}
	if(num==0){
		return true;
	}
}
int main(){
	int T;
	cin>>T;
	int j=T;
	long long num;
	while(T--){
		cin>>num;
		while(!isUpNum(num)){
			num++;
		}
		cout<<"case #"<<j-T-1<<":"<<endl;
		cout<<num<<endl;
	}
}
//别人思路及代码 https://blog.csdn.net/lecholin/article/details/77916349
	最自然的想法是，通过扫描s[i] < s[i+1]找到上升点，然后对上升点前的s[i-1]+1，后面全部填0。但是要考虑到s[i-1]+1后可能会破坏前面的非上升序列，因此还要将前面的元素考虑进来。

采取的办法是，在扫描上升点的同时，维护经过的最小数字及位置，找到上升点后，判断s[i-1]+1和该最小数字的大小，如果s[i-1]+1更小，那就在后面填0即可，否则要对最小数字+1，并在其后全填0。（实质是让填0前的那个数字保持最小）
例子：7400920的上升点在第二个0和9之间，如果变成7101000不满足“非上升”，但是变成7410000则满足。
#include <iostream>
using namespace std;
int main()
{
    int kase;
    cin >> kase;
    string s;
    for(int t = 0; t < kase; ++t)
    {
        cin >> s;
        int min_num = 10, min_pos = 0; //最小数字及所在小标
        for (int i = 0; i < s.size()-1; ++i)
        {
            if (s[i] < s[i+1]) //出现上升
            {
                int tmp = s[i] - '0' + 1, pos = (tmp>min_num)?min_pos:i; //pos为更新的位置
                //要更新的数字加1，后面全填0
                s[pos]++; 
                for(int j = pos + 1; j < s.size(); ++j)
                    s[j] = '0';
                break;
            }
            else if (s[i]-'0' < min_num) //维护经过的最小数字
            {
                min_num = s[i] - '0';
                min_pos = i;
            }
        }
        cout << "case #" << t << ':' << endl;
        cout << s << endl;
    }
    return 0;
}

2.四位数加法

#include<bits/stdc++.h>
using namespace std;
//求分子分母最大公倍数
long long getMaxCommonMultiple(long long mother,long long son){
	long long min ;
	if(mother>son){
		min=son;
	}else if(mother<son){
		min=mother;
	}else{
		return son;
	}
    //缺考虑了
	if(son%mother==0){
		return mother;
	}
	long long i;
	for(i=(long long)sqrt(min);i>0;i--){
		if(mother%i==0&&son%i==0){
			return i;
		}
	}
	//如果i==1说明没有公倍数，提示函数调用者即可
	if(i==1){
		return 1;
	}
	
}
long long FractionSum(int aaaabbbb, int ccccdddd) { 
   int a,b,c,d;
   long long son,mother;
   a=aaaabbbb/10000;
   b=aaaabbbb%10000;
   c=ccccdddd/10000;
   d=ccccdddd%10000;
   mother=b*d;
   son=a*d+c*b;
   long long i=getMaxCommonMultiple(mother,son);
   if(i==1){
   	 return son*100000000+mother;
   }else{
   	 son/=i;
   	 mother/=i;
   	 return son*100000000+mother;
   }

}
int main(){
    int a, b, c, d;
    long long r;
    scanf("%d%d%d%d", &a, &b, &c, &d);
    r = FractionSum(a * 10000 + b, c * 10000 + d);

    printf("%d/%d+%d/%d=%lld/%lld.\n", a, b, c, d,
           r / 100000000, r % 100000000);
    return 0;
}

3.进制转换

//1.初始思路，超时。。。。
#include<bits/stdc++.h>
using namespace std;

bool isTrue(long long num,int ary,int m){
	int arr[200];
	int i=0,cnt=0;
	do{
	   arr[i]=num%ary;
	   num/=ary;
	   i++;	
	}while(num!=0);
	for(int j=0;j<i;j++){
		if(arr[j]==0){
			cnt++;
		}else{
			break;
		}
	}
	if(cnt==m){
		return true;
	}else{
		return false;
	}
}
int main(){
	long long l,r;
	int k,m,T; 
	cin>>T;
	while(T--){
		cin>>l>>r>>k>>m;
		int cnt=0;
		for(;l<r;l++){
			if(isTrue(l,k,m)){
				cnt++;
			}
		}
		cout<<cnt<<endl; 
	}
} 
//2.更新、中途break 也超时。。。
#include<bits/stdc++.h>
using namespace std;
bool isTrue(long long num,int ary,int m){
	for(int i=0;i<m;i++){
		if(num%ary==0&&num>0){
			num/=ary;
		}else{
			return false;
		}
	}
	if(num%ary!=0){
		return true;
	}
}
int main(){
	long long l,r;
	int k,m,T; 
	cin>>T;
	while(T--){
		cin>>l>>r>>k>>m;
		int cnt=0;
		for(;l<r;l++){
			if(isTrue(l,k,m)){
				cnt++;
			}
		}
		cout<<cnt<<endl; 
	}
} 
//大佬思路
题目要求的时在区间范围内的m进制后有k个零的数有多少，很容易想到如果一个数的m进制后有k个零，就一定能被m^k整除，而在含k个零中，一定存在含k+1个零的（含k+1个零就意味着一定含k个零），在1，2，3....x中，能被m^k整除的有⌊x/m^k⌋个，所以只含k个零的个数有ansx = ⌊x/m^k⌋-⌊x/m^k+1⌋，区间的话就是ansr - ansl-1 注意是l-1
但是有个问题，就是直接计算mk 会溢出的问题，而且又不能取模，根据式子，就要用到除法，如果溢出了，相除肯定变成了0（据说long double好像也行，我没试过）
#include<bits/stdc++.h>
using namespace std;

int main(){
	long long l,r;
	int k,m,T; 
	cin>>T;
	while(T--){
		cin>>l>>r>>k>>m;
		l--;//这步为什么 
		long long rf=r,lf=l;
		for(int i=0;i<m;i++){
			rf=(long long)(rf/k);
			lf=(long long)(lf/k);
		}
		long long rfs=(long long)(rf/k);
		long long lfs=(long long)(lf/k);
		cout<<rf-lf-rfs+lfs<<endl;
	}
}

4.斐波那契求和

#include<bits/stdc++.h>
using namespace std;

struct Fraction{
	unsigned long long up,down;
};
long long gcd(long long a,long long b){
	if(b==0) return a;
	else return gcd(b,a%b);
	
}
Fraction reduce(Fraction c){
	//求出两个数最大公约数
	long long maxC = gcd(c.down,c.up);
	c.down/=maxC;
	c.up/=maxC;
	return c;
}
//分数加法
Fraction add(Fraction a,Fraction b){
	Fraction c;
	c.down=a.down*b.down;
	c.up=a.up*b.down+b.up*a.down;
	return reduce(c);//约分 
}
int main(){
	int T;
	cin>>T;
	while(T--){
	int N;
	cin>>N;
//	N=N+1;//不知道为什么。。。整体少加了一位 
	unsigned long long f[N+2];
	f[1]=1,f[2]=1;
	for(int i=3;i<=N+2;i++){
		f[i]=f[i-1]+f[i-2];
	 }
	Fraction fraction[N+1];//用来存分数
//	cout<<f[3]<<f[1]+f[2]<<endl;
//	f[3]%=10;//在N未加1时，为什么这里的f[3]是52... 
//	cout<<f[3]<<f[1]+f[2]<<endl;
	for(int i=1;i<=N;i++){
		fraction[i].up=f[i+2];
		fraction[i].down=f[i+1];
	}
	Fraction result;
	result=fraction[1];
//	 cout<<result.up<<"/"<<result.down; 
	 for(int i=2;i<=N;i++){
		result=add(result,fraction[i]);
	 }
	 cout<<result.up<<"/"<<result.down; 
	}
}

5.统计单词个数

#include<bits/stdc++.h>
using namespace std;

int main(){
	set<string> s;
	s.insert("for");
	s.insert("of");
	s.insert("a");
	s.insert("an");
	s.insert("the");
	s.insert("and");
	int T;
	string line;
	int cur=0;
	cin>>T;
	cin.get();//取得第一个回车符 
	while(T--){
		int cnt=0;
		set<string> set;
		set=s;
		getline(cin,line);//取得未知个数字符串
		for (auto &i : line){//把单个字符都转变为小写 
            i = tolower(i); 
        }
        string temp;
        istringstream iss(line);
        while(iss>>temp){//取得以空格为分隔符的字符串
        	set.insert(temp);
        	if(set.size()==7){
        		set.erase(temp);
        		cnt++;
			}
		}
        cout << "case #" << cur++ << ":\n" <<cnt<< '\n';      
	}
}

6.爬阶梯问题

#include<bits/stdc++.h>
using namespace std;
//这种题目从结果反推原因，比如说你在第五号台阶，那你前面一步可能情况时在第一、第二、第三、第四个台阶，就把这些可能相加即可。
int main(){
	unsigned long long a[51];
	a[1]=1;
	a[2]=2;
	a[3]=4;
	a[4]=8;
	for(int i=5;i<=50;i++){
		a[i]=a[i-1]+a[i-2]+a[i-3]+a[i-4];
	}
	int T;
	cin>>T;
	int cur=T;
	while(T--){
		cout<<"case #"<<cur-T-1<<":"<<endl;
		int n;
		cin>>n;
		cout<<a[n]<<endl;
	}
	
}

7.找数字

//运行错误，利用桶排序，但是测试数据有负数加正整数
#include<bits/stdc++.h>
using namespace std;

int main(){
	int N;
	while(cin>>N){
		int cur=N;
		int n;
//		int a[N];
        int b[N];
		for(int j=0;j<N;j++){
			b[j]=0;
		}
//		memset(a,0,cur);
//        cout<<(1<<31)-1<<endl;
        int min=(1<<31)-1;
        int k=0;
		while(N--){
		scanf("%d",&n); 
		   if(min>n){
		   	 min=n;
		   }
		   b[k++]=n;	
		}
		min=abs(min);
		int a[min+cur];
		for(int j=0;j<cur+min;j++){
			a[j]=0;
		}
		for(int j=0;j<cur;j++){
			a[b[j]+min]++;
		}
		for(int i=0;i<cur;i++){
			if(a[i]>cur/2){
				cout<<i-min<<endl;
			}
		}
	}
} 
//大佬思路
#include<bits/stdc++.h>
using namespace std;

int main(){
	int N,temp;
	while(cin>>N){
		int res=0;
		int cnt=0;
		for(int i=0;i<N;i++){
			scanf("%d",&temp);
		    if(cnt==0){
		    	res=temp;//res上面一个数据,temp当前数据
		    	cnt++;
			}else if(temp==res){
				cnt++;
			}else {
				cnt--;
			}
		}
		cout<<res<<endl;
	}
}

8.数据压缩

#include<bits/stdc++.h>
using namespace std;
//发现题目在调试后才能ac,rubbish
int main(){
	int N;
	while(cin>>N){
		getchar();
		int n=0;
		while(N--){    
			string str;
			getline(cin,str);
			cout<<"case #"<<n++<<":"<<endl;
			int cur=1;
			char c;
			for(int i=0;i<str.length();i++){//这里刚好在i+1==str.length(),a[i+1]=='\0';没报异常，如果声明数组则会溢出
				c=str[i];
				if(c==str[i+1]){
					cur++;
					if(cur==255){
						cout<<"255"<<c;
						cur=0; 
					}
				}
				if(c!=str[i+1]&&cur!=0){//当输入数据刚好255时，禁止输出
					cout<<cur<<c;
					cur=1;
				}
			}
			cout<<endl;
		}
	}
}

9.max max sum

//初始思路，getline()得到的字符串如果有负号就会出现问题
#include<bits/stdc++.h>
using namespace std;

int main(){
	string str;
	int s[100000];//存各区间和数组 
	memset(s,0,sizeof(s));
//	cout<<s[0]<<endl;
	while(getline(cin,str)){
	  int interval = str[0]-'0';
	  int nums = str[2]-'0';
	  int sum=0;
	  queue<int> q; 
	  //求解第一个interval的sum,并压入队列 
	  for(int i=4;i<2*interval+4;i+=2){
//	  	cout<<i<<" "<<str[i]<<endl;
	  	sum+=(str[i]-'0');
	  	q.push(str[i]-'0');
	  }
	  s[0]=sum;
	  int k=1;
	  for(int j=2*interval+4;j<str.length();j+=2){
	  	 q.push(str[j]-'0');
	  	 sum+=(str[j]-'0');
	  	 sum-=(q.front());
	  	 q.pop();
	  	 s[k++]=sum;
	  }
	  for(int i=0;i<k;i++){
	  	cout<<s[i]<<" ";
	  }
	  cout<<endl;
		
    }
}
//更新二版，提交出错，不知道什么原因。。。测试数据可以，可能数据量大吧
#include<bits/stdc++.h>
using namespace std;
int maxsub(int a[],int length){
	int thisSum=0,maxSum=-1001;
	for(int i=0;i<length;i++){
		thisSum+=a[i];
		if(thisSum>maxSum){
			maxSum=thisSum;
		}
		if(thisSum<0){
			thisSum=0;
		}
	}
	return maxSum;
	
}
int main(){
	int interval;
	int nums;
	while(cin>>interval>>nums){
		int s[nums];
		memset(s,0,sizeof(s));
		int i=0;
		while(nums--){
			scanf("%d",&s[i++]);
		}
		
		queue<int> q;
		int sums[i];//存储区间和 
		int sum=0;
		for(int i=0;i<interval;i++){
			sum+=s[i];
			q.push(s[i]);
		}
		memset(sums,0,sizeof(sums));
		sums[0]=sum;
		int k=1;
		for(int j=interval;j<i;j++){
			q.push(s[j]);
			sum+=s[j];
			sum-=q.front();
			q.pop();
			sums[k++]=sum;
		}
		cout<<maxsub(sums,k)<<endl;; 
//		for(int i=0;i<k;i++){
//	  	cout<<sums[i]<<" ";
//	    }
//	    cout<<endl;
	} 
}
//大佬利用动态规划
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int   MAXN = 1e6 + 10;
const int INF = 0x3f3f3f3f；//10亿

int dp[MAXN], a[MAXN], mmax[MAXN];

int main()
{
    int n, m, Max;
    while(scanf("%d%d", &m, &n) != EOF)
    {
        memset(dp, 0, sizeof(dp));
        memset(mmax, 0, sizeof(mmax));
        for(int i = 1; i <= n; i++)
            scanf("%d", &a[i]);
        for(int i = 1; i <= m; i++)
        {
            Max = -INF;
            for(int j = i; j <= n; j++)
            {
                dp[j] = max(dp[j - 1] + a[j], mmax[j - 1] + a[j]);
                mmax[j - 1] = Max;
                Max = max(Max, dp[j]);
            }
        }
        printf("%d\n", Max);
    }
    return 0;
}

10.找规律

#include<bits/stdc++.h>
using namespace std;
//被迫用C？ 
int main(){
	int N;
	scanf("%d",&N);
	while(N--){
		int num;
		scanf("%d",&num);
		if(num==1){
			printf("1\n");
			continue;
		}
		num--;
		int i=sqrt(num<<1);
		if((i*(i+1))>>1==num){//右移动比除法快 
			printf("1\n");
		}else{
			printf("0\n");
		}
	}
}

打赏一个呗

取消

感谢您的支持，我会继续努力的!

扫码支持
扫码支持
扫码打赏，你说多少就多少

打开支付宝扫一扫，即可进行扫码打赏哦