10.27 아 례 시험 문제

T1 링크http://lk.yali.edu.cn/contest/3/problem/13
Description
함수 f (x) 를 x 를 구성 하 는 여러 숫자의 합 으로 정의 합 니 다. 예 를 들 어 f (2018) = 2 + 0 + 1 + 8 = 11. 정수 n 을 지정 하여 모든 만족 조건 f (x) + x = n 의 x 를 구하 십시오.
Input
모두 한 줄, 하나의 정수 n.
Output
첫 번 째 줄 의 정수 ans 는 몇 개의 정수 x 가 조건 을 만족 시 키 는 지 나타 낸다.다음 에 ans 줄 을 연결 하면 각 줄 의 정 수 는 조건 을 만족 시 키 는 x 를 나타 낸다.x. 작은 것 부터 큰 것 까지 순서대로 출력 합 니 다.
Samples
http://lk.yali.edu.cn/download.php?type=problem&id=13
Constraints
30% 의 데이터 만족: n ≤ 1000 대 100% 의 데이터 만족: n ≤ 10 ^ 18 Time limit: 1s Memory limit: 512 MB
제목 분석
이 문 제 를 얼핏 보면 성격 이 별로 없 는 것 같 아서 30 부분 만 나 눠 주면 떠 날 수 있 을 것 같다.다시 한 번 보 겠 습 니 다. 제목 에 f (x) + x = n, f (x) 를 x 를 구성 하 는 여러 숫자의 합 으로 정의 합 니 다.이것 은 무엇 을 설명 합 니까?첫째: x 는 n 보다 작 아야 한다.제2 f (x) 는 최대 17 이다.×9. 그래서 x 가 n 보다 17 작 으 면×9 이상 이면 우 리 는 답 을 얻 을 수 없다.n 의 범위 때문에.그래서 우 리 는 앞으로 매 거 할 수 있 고 매번 매 거 할 때마다 17 을 넘 지 않 는 다.×9. 답 을 얻 을 수 있다.

#include
#include
#include
#include
#include
using namespace std;
long long n,a[100];
int cnt;
int main() {
	scanf("%lld",&n);
	if(n<=1e6) {// if           ，           ３０ ＱＷＱ
		for(register int i=1;i<=n;++i) {
			int tt=i,sum=0;
			while(tt) { sum+=tt%10; tt/=10; }
			if(sum+i==n) a[++cnt]=i;
		}
		if(!cnt) {cout<<cnt<<endl;return 0;}
		cout<<cnt<<endl;
		for(register int i=1;i<=cnt;++i) cout<<a[i]<<endl;
	}
	else {
		int nn=0;long long tmp1=n;
		while(n) { nn+=n%10; n/=10; }
		n=tmp1;
		while(n>(tmp1-500)) {
			long long tt=n;int sum=0;
			while(tt) { sum+=tt%10; tt/=10; }
			if(sum+n==tmp1) a[++cnt]=n;
			n--;
		}
		if(!cnt) {cout<<cnt<<endl;return 0;}
		cout<<cnt<<endl;
		for(register int i=cnt;i>=1;--i) cout<<a[i]<<endl;
	}
	return 0;
}

T2 Description
두 문자열 s, t 와 정수 k 를 보 여 줍 니 다. 다음 작업 을 수행 합 니 다.
11 부터 length (s) 까지 s 에서 K 개의 교차 하지 않 는 연속 적 인 비 빈 문자열 p1,..., pk 를 순서대로 선택 합 니 다.
11 부터 length (t) 까지 t 에서 K 개의 교차 하지 않 는 연속 적 인 비 빈 문자열 q1,..., qk 를 순서대로 선택 합 니 다.
p1,..., pk 가 s 에서 상대 적 인 위치 순 서 를 유지 하고 q1,..., qk 가 t 에서 상대 적 인 위치 순 서 를 유지 합 니 다.
p1 = q1, p2 = q2,..., pk = qk 를 최대 화하 고 선택 한 k 문자열 의 길 이 를 합 칩 니 다.
그 중에서 문자열 은 1 부터 레이 블 을 표시 하고 length (s) 는 문자열 s 의 길 이 를 표시 합 니 다.Input
첫 번 째 줄 의 세 개의 정수 n, m, k 는 각각 문자열 s, t 의 길 이 를 나타 내 고 선택 한 하위 문자열 의 개 수 를 나타 낸다.
두 번 째 줄 문자열 s.
세 번 째 줄 문자열 t.
문자열 은 소문 자로 만 구성 되 어 있 습 니 다.Output
한 줄 의 정 수 는 선택 한 하위 문자열 의 길이 와 최대 치 를 나타 낸다.Sample 1 Input
15 9 4 ababaaabbaaaabb bbaababbb
Output
8
Explanation
문자열 의 모든 문 자 를 1 부터 표시 합 니 다.
s 에서 순서대로 선택 한 4 개의 교차 하지 않 는 빈 문자열 은 [2, 2], [4, 5], [7, 8], [13, 15] 이다.
t 에서 순서대로 선택 한 4 개의 교차 하지 않 는 빈 문자열 은 [1, 1], [2, 3], [4, 5], [6, 8] 이다.
대응 문자열: "b", "ba", "ab", "abb", "b", "ba", "ab", "abb" 샘플 2http://lk.yali.edu.cn/download.php?type=problem&id=14
함부로 사 기 를 치 는 것 을 방지 하기 위해 서 이 문 제 는 묶음 테스트 를 채택 한다.
subtask1 20pts : n,m≤10,k≤2.
subtask2 25pts : n,m≤100,k≤3.
subtask3 25pts : n,m≤1000,k=1 .
subtask4 30pts : n,m≤1000,k≤10.
Time limit : 1s
Memory limit : 512MB

#include
#include
#include
#include
#include
using namespace std;
char a[1005],b[1005];
int n,m,k,ans,ff[1005][1005][15][2];
inline int check(int a,int b,int c,int d) {
	
}
int main() {
	cin>>n>>m>>k;
	scanf("%s%s",a+1,b+1);
	for(register int i=1;i<=n;++i)
		for(register int j=1;j<=m;++j)
			for(register int kk=1;kk<=k;++kk){
				ff[i][j][kk][1]=max(ff[i][j-1][kk][1],ff[i-1][j][kk][1]);
		//             ，            ，     for       
				if(a[i]==b[j]) {
					ff[i][j][kk][0]=max(ff[i-1][j-1][kk-1][1],ff[i-1][j-1][kk][0])+1;//                              
					ff[i][j][kk][1]=max(ff[i][j][kk][0],ff[i][j][kk][1]);
				}//      
			}
	cout<<ff[n][m][k][1]<<endl;
	return 0;
}