A. Display The Number
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
You have a large electronic screen which can display up to 998244353 decimal digits. The digits are displayed in the same way as on different electronic alarm clocks: each place for a digit consists of 7 segments which can be turned on and off to compose different digits. The following picture describes how you can display all 10 decimal digits:
As you can see, different digits may require different number of segments to be turned on. For example, if you want to display 1, you have to turn on 2 segments of the screen, and if you want to display 8, all 7 segments of some place to display a digit should be turned on.
You want to display a really large integer on the screen. Unfortunately, the screen is bugged: no more than n segments can be turned on simultaneously. So now you wonder what is the greatest integer that can be displayed by turning on no more than n segments.
Your program should be able to process t different test cases.
Input
The first line contains one integer t (1≤t≤100) — the number of test cases in the input.
Then the test cases follow, each of them is represented by a separate line containing one integer n (2≤n≤105) — the maximum number of segments that can be turned on in the corresponding testcase.
It is guaranteed that the sum of n over all test cases in the input does not exceed 105.
Output
For each test case, print the greatest integer that can be displayed by turning on no more than n segments of the screen. Note that the answer may not fit in the standard 32-bit or 64-bit integral data type.
题意：给了1~9中每个数字需要多少个木棍组成
然后选择给了你n个木棍 求能表示的最多数字
思路：可以发现 我们优先让能表示的数字越多 则越多 因为位数多 肯定比位数少的大
那么 要求花的木棍比较少 所以就是数字1 一个1要两个木棍
如果木棍个数是偶数 只要输出n/2个1就好
如果是奇数 多了一个木棍 我们发现三个木棍可以组成一个7 所以输出一个7 然后输出
(n-3)/2个1即可
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define me(a,x) memset(a,x,sizeof a)
#define pb(a) push_back(a)
#define pa pair<int,int>
#define fi first
#define se second
int main()
{
int t;cin>>t;
while(t--){
int n;
cin>>n;
if(n&1) cout<<7,n-=3;
int num=n/2;
while(num--) cout<<1;
puts("");
}
return 0;
}
B. Infinite Prefixes
time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
You are given string s of length n consisting of 0-s and 1-s. You build an infinite string t as a concatenation of an infinite number of strings s, or t=ssss… For example, if s= 10010, then t= 100101001010010…
Calculate the number of prefixes of t with balance equal to x. The balance of some string q is equal to cnt0,q−cnt1,q, where cnt0,q is the number of occurrences of 0 in q, and cnt1,q is the number of occurrences of 1 in q. The number of such prefixes can be infinite; if it is so, you must say that.
A prefix is a string consisting of several first letters of a given string, without any reorders. An empty prefix is also a valid prefix. For example, the string “abcd” has 5 prefixes: empty string, “a”, “ab”, “abc” and “abcd”.
Input
The first line contains the single integer T (1≤T≤100) — the number of test cases.
Next 2T lines contain descriptions of test cases — two lines per test case. The first line contains two integers n and x (1≤n≤105, −109≤x≤109) — the length of string s and the desired balance, respectively.
The second line contains the binary string s (|s|=n, si∈{0,1}).
It’s guaranteed that the total sum of n doesn’t exceed 105.
Output
Print T integers — one per test case. For each test case print the number of prefixes or −1 if there is an infinite number of such prefixes.
题意：就是说给了一个字符串 和一个数字x
然后 说你可以让无数个这个字符串拼接在一起
问让前缀0的个数减去前缀1的个数 为x的 前缀个数有多少种
思路：前缀和 记录下num(0)-num(1) 如果最后一个的差为0 那么就是无限个 或者0个 需要判断一下 其他的 只要取枚举长度 x-前缀的差 看x是不是能被整个字符串的差整除即可
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define me(a,x) memset(a,x,sizeof a)
#define pb(a) push_back(a)
#define pa pair<int,int>
#define fi first
#define se second
int a[200005],b[200005],qz[200005];
string s;
void solve()
{
map<ll,ll>mp;
ll n,x;
cin>>n>>x>>s;
qz[0]=0;
for(int i=0; i<n; i++)
if(s[i]=='0')
qz[i+1]=qz[i]+1;
else
qz[i+1]=qz[i]-1;
if(!qz[n])
{
int f=0;
for(int i=0; i<=n; i++) if(qz[i]==x) {f=1;break;}
puts(f?"-1":"0");
}
else
{
ll qq=0;
for(int i=0; i<=n; i++)
{
ll tt=x-qz[i];
if(!(tt%qz[n]))
{
if(tt/qz[n]>=0 && !mp[(tt/qz[n])*n+i])
{
qq++;
mp[(tt/qz[n])*n+i]=1;
}
}
}
printf("%lld\n",qq);
}
}
int main()
{
int T;
cin>>T;
while(T--) solve();
return 0;
}
C. Obtain The String
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
You are given two strings s and t consisting of lowercase Latin letters. Also you have a string z which is initially empty. You want string z to be equal to string t. You can perform the following operation to achieve this: append any subsequence of s at the end of string z. A subsequence is a sequence that can be derived from the given sequence by deleting zero or more elements without changing the order of the remaining elements. For example, if z=ac, s=abcde, you may turn z into following strings in one operation:
z=acace (if we choose subsequence ace);
z=acbcd (if we choose subsequence bcd);
z=acbce (if we choose subsequence bce).
Note that after this operation string s doesn’t change.
Calculate the minimum number of such operations to turn string z into string t.
Input
The first line contains the integer T (1≤T≤100) — the number of test cases.
The first line of each testcase contains one string s (1≤|s|≤105) consisting of lowercase Latin letters.
The second line of each testcase contains one string t (1≤|t|≤105) consisting of lowercase Latin letters.
It is guaranteed that the total length of all strings s and t in the input does not exceed 2⋅105.
Output
For each testcase, print one integer — the minimum number of operations to turn string z into string t. If it’s impossible print −1.
题意：给了两个字符串 s和t 让构造一个字符串z 使得z等于t
z可以由字符串s的序列中获取 问最小操作数
思路：如果字符串t中的字母 s中不存在 那么就是-1
否则就一定可以 那么暴力找的话 复杂度就是两个字符串长度的乘积 显然不可取
所以 我们可以这样 ans[i][j]表示i位置的下一个字符串为j的位置
这样整体复杂度只要O(len(t))
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define me(a,x) memset(a,x,sizeof a)
#define pb(a) push_back(a)
#define pa pair<int,int>
#define fi first
#define se second
string s,t;
int a[200005],b[200005],ans[200005][30];
void Init()
{
for(int i=0; s[i]; i++)
a[i+1]=s[i]-'a'+1;
for(int i=0; t[i]; i++)
b[i+1]=t[i]-'a'+1;
int len=s.size();
for(int i=1; i<=26; i++)
ans[len+1][i]=len+1;
}
void solve()
{
Init();
int e=s.size();
for(int i=e; i>=1; i--)
{
for(int j=1; j<=26; j++)
{
if(a[i]==j)
ans[i][j]=i;
else
ans[i][j]=ans[i+1][j];
}
}
int q=1,ok=0;
int len=t.size();
while(q<=len)
{
ok++;
if(ans[1][b[q]]-1==e)
break;
int num=1;
while(ans[num][b[q]]!=e+1&&q<=len)
{
num=ans[num][b[q]]+1;
q++;
}
}
if(q-1==len)
printf("%d\n",ok);
else
puts("-1");
}
int main()
{
int T;
cin>>T;
while(T--){
cin>>s>>t;
solve();
}
return 0;
}
PROBLEMSSUBMIT CODEMY SUBMISSIONSSTATUSHACKSSTANDINGSCUSTOM INVOCATION
D. Same GCDs
time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
You are given two integers a and m. Calculate the number of integers x such that 0≤x<m and gcd(a,m)=gcd(a+x,m).
Note: gcd(a,b) is the greatest common divisor of a and b.
Input
The first line contains the single integer T (1≤T≤50) — the number of test cases.
Next T lines contain test cases — one per line. Each line contains two integers a and m (1≤a<m≤1010).
Output
Print T integers — one per test case. For each test case print the number of appropriate x-s.
题意 ：给了a和m 现在问gcd(a,m)=gcd(a+x,m) 且0≤x＜m 满足的x的个数有多少个
思路：
记gcd(a,m)=k gcd(a+x,m)=gcd((a+x)%m,m)=k
因为gcd(a,b)=gcd(b,a%b) 这里代入一下 a+x和m 即可知道上式
记(a+x)%m=b
则有 0≤b＜m 即gcd(b,m)=k 且b＜m
则 gcd(b/k,m/k)=1 b/k＜m/k
所以就是求euler(m/k) 也就是在1~m/k间 与m/k互质的数的个数
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define me(a,x) memset(a,x,sizeof a)
#define pb(a) push_back(a)
#define pa pair<int,int>
#define fi first
#define se second
ll a,m;
ll el(ll x)
{
ll q=x,w=x;
for(ll i=2; i*i<=w; i++){
if(w%i==0){
while(w%i==0) w/=i;
q=q/i*(i-1);
}
}
if(w>1) q=q/w*(w-1);
return q;
}
void solve()
{
int T;cin>>T;
while(T--){
cin>>a>>m;
cout<<el(m/__gcd(a, m))<<endl;
}
}
int main()
{
solve();
return 0;
}
看完如果觉得写的还不错 能看懂 麻烦给个赞 码字不易
有更好的更简单的做法的 也欢迎大佬指教
京公网安备 11010502036488号