T1 除数减法
给定一个整数 n，按照如下算法进行操作：
1、如果 n=0，结束算法；
2、找到 n的最小质因子 d ；
3、n−=d并回到操作 1 。
一行一个整数 t 表示测试的数量（1 <= t <= 10000）。
后面 t 行，每行一个整数 n（2 <= n <= 10^9）。
思路
这题是一个结论题， 先找到最小的一个质因子p1。 （n-p1）/2+1，得到答案后直接输出。
#include
#include
#include
using namespace std;
int findMinFactor(int n)
{
for (int i = 2; i * i <= n; i ++ )
{
if(n % i == 0)
return i;
}
return n;
}
int main()
{
int t,n;
cin >> t;
while(t -- )
{
int ans=0;
scanf("%d", &n);
int minfac=findMinFactor(n);
n-=minfac;
cout << n/2+1 << endl;
}
return 0;
}
T2，数组构造
描述
给出 2个数字 x 和 y，以及一个长度 l，你来找一个等差数列，满足以下条件：
-
数列中包含 x 和 y
-
数列中所有的数均为正数
-
数列的长度为 l
-
如果有多组满足条件的，找出所有数字之和最小的
输出这个最小和。
输入
第一行仅有一个整数 T ( 1 <= T <= 100000 ) ，表示测试数据的组数。
每组数据仅有一行，包含三个整数 l ,x 和 y ( 2 <= l ,x < y <= 1e6) ，分别表示数列的长度和数列中的两个元素的值。
输出
对每一组测试数据，输出一个数，对应等差数列的最小和。
数据范围
( 1 <= T <= 100000 , 2 <= l ,x ,y <= 1e6）
输入样例
10
2 1 49
5 20 50
6 20 50
7 20 50
8 20 50
5 3 8
9 13 22
999997 99997 1000000
2 1 2
3 1 3
输出样例
50
150
210
224
232
65
117
500000499994
3
6
样例解释
1. 选 1 49
2. 选 10 20 30 40 50
3. 选 20 26 32 38 44 50
4. 选 3 8 13 18 23
5. 选 1 4 7 10 13 16 19 22 25
思路
我们考虑这个等差数列的公差，一定是 y−x 的约数，求出所有 y−x 的约数。
对于每一个约数，为了让和更小，需要让首项 fir 最小（0
记录所有约数中最小的最小公差，就是计算结果。
解法一，暴力搜索，TLE。
#include
#include
#include
using namespace std;
typedef long long LL;
LL solution(LL l, LL x , LL y)
{
LL sum=6e17;
// i 代表x到y之间有多少个数,最多有l-2，或者y-x-1。
for (LL i = min(l-2,y-x-1); i >= 0; i -- )
{
if((y-x)%(i+1)==0)
{
LL gc = (y-x)/(i+1);// 求出公差
LL left, j = l-2-i;
while (x-j*gc<=0)j--;// j 为在x 左边的个数
left = x-j*gc; // 求出左端点
// cout <<"left "<< left << endl;
LL right = (l-2-i-j)*gc+y;// 求出右端点
// cout <<"right "<< right << endl;
if(right > sum || (left+right)*l/2<0) continue;// 预防卡ＬＬ，导致sum<0。
sum = min(sum, (left+right)*l/2);// 等差数列求解
}
}
return sum;
}
int main()
{
int t;
cin >> t;
while (t -- )
{
LL l,x,y;
scanf("%lld%lld%lld",&l, &x, &y);
printf("%lldn",solution(l,x,y));
}
return 0;
}
解法二，优化版。
#include
#include
#include
#include
using namespace std;
typedef long long LL;
vector findAllFactors(LL a)// 找到y-x所有的可能的约数。
{
vector factors;
for (int i = 1; i * i <= a; i++)
{
if (a % i == 0)
{
factors.push_back(i);
if (i != a / i)
factors.push_back(a/i);
}
}
//sort(factors.begin(), factors.end());//从小到大排列
return factors;
}
LL solution(LL l, LL x , LL y)
{
LL sum=6e17;
vector C = findAllFactors(y-x);
// 遍历所有的约数
for(auto gc:C)
{
LL i = (y-x) / gc -1;//表示在x到y中间的数有i个数。
if( i+2 > l) continue;// 如果xy中间的数量+2大于l，则退出这层循环。
LL j = x/gc;// 表示在x左边的最多的个数。
if(x%gc == 0) j--; // 表示在x左边的个数。
if(j<0)j=0;// 考虑到， j 可能一开始为0，如果j<0 则让j = 0；
j = min(l-2-i,j);// 在x左边的数
LL left = x-j*gc;//左端点
LL right = left+(l-1)*gc;// 右端点
if(right > sum || (left+right)*l/2<0) continue;// 预防卡ＬＬ，导致sum<0。
sum = min(sum, (left+right)*l/2);
// cout<< gc <<" "<< left << " " << right << endl;
}
return sum;
}
int main()
{
int t;
cin >> t;
while (t -- )
{
LL l,x,y;
scanf("%lld%lld%lld",&l, &x, &y);
printf("%lldn",solution(l,x,y));
}
// auto C = findAllFactors(999999);
// for (auto c:C ) cout<
T3 字符串删除
给你一个 01 字符串 s，如果 si=1 且 si+1=0，则可以删除其中一个，问经过若干次删除操作后，使字符串最短，且字典序最小的字符串，请输出这个字符串。
输入
第一行仅有一个正整数 t ( 1 <= t <= 1000 )，表示测试数据的组数。
对于每组测试数据，包括一个由字符 0 和字符 1 组成的字符串s，s的长度小于1000。
输出
共有 t 行，依次对应各组测试数据的结果。
数据范围
1 <= t <= 1000
输入样例
5
0001111111
0101
11001101
1110000000
1
输出样例
0001111111
001
01
0
1
样例解释
在第一个样例中，不能执行任何动作。
在第二个样例中，应该擦除 s2。
在第三个样例中，按照以下顺序删除： 11001101 →→ 1100101 →→ 110101 →→ 10101 →→ 1101 →→ 101 →→ 01
思路
我们先考虑有哪些是无法消除掉的，首先前缀的 0是无法消除掉的，后缀的 1 也是无法消除掉的。
例如：00100110011
前面 2 个 0 ，后面 2 个 1 是无法消除的。
一连串的 11…1100…0011…1100…00 最终都可以转为 1 或 0，我们先认为转换后的字符是 ?。
除了前缀 0 ，后缀 1，中间的部分一定是多个这样的串组成的（也可能是 0 个，比如：00110011）。
那么多个这样的串最终都可以转为多个 ?。我们发现，多个 ? 我们可以通过选择变化成不同的 01，最终都转为一个 0。
因此我们保留前缀 0 后缀 1 ，剩下的中间部分如果存在，则变成一个 0（字典序最小），否则什么都不必添加。
#include
#include
#include
using namespace std;
int main()
{
int t;
cin >> t;
while (t --)
{
string s;
cin >> s;
if(s.size()==1)
{
cout << s <=0; i--)
{
if(s[i]=='0')break;
else b1+=s[i];
}
if(f0.size() + b1.size() == s.size())// 如果前后中间没有东西不加0.
cout << f0 << b1 << endl;
else
cout << f0 << 0 << b1 << endl;
}
return 0;
}
T4 机器翻译V2
第一行输入一个n(n<=100000)，表示词典中单词的个数。
接下来n行，每行两个单词，表示原始单词以及这个单词对应的意思。
接下来一行，输入一段文本，表示需要翻译的文章。
(每个单词长度不超过5且单词间以空格隔开，整个文本单词个数不超过100000)
输入样例
3
a ds
c de
b fr
c b a
输出样例
de fr ds
样例解释
cc 被翻译成 dede，bb 被翻译成 frfr，aa 被翻译成 dsds，因此：c b ac b a 对应 de fr dsde fr ds。
#include
#include
#include
#include
#include
using namespace std;
unordered_map p;
int main()
{
int n;
string a,b;
cin >> n;
for (int i = 1; i <= n; i ++ )
{
cin >> a >> b;
p[a]=b;
}
for (int i = 1; i <= n; i ++ )
{
string x;
cin >> x;
cout << p[x] << ' ';
}
return 0;
}
