蚂蚁9.15笔试
没有竞赛难度的题，整体难度适中吧
#蚂蚁笔试##蚂蚁2023秋招笔试凉了啊#
1:反向求解即可
2.入门树形dp遍历遍即可
3.状压前缀和。稍后上代码
1.简单统计即可
public class first {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(),k = 0;
StringBuilder s = new StringBuilder();
while (n>0){
if((n&1)==1)
s.append((char)(k+'a'));
n = n>>1;
k++;
}
System.out.println(s);
}
} 2.简单统计，不过要输出-1这种可能，题目貌似没说 public class second {
static Map<Integer, List<Integer>> m = new HashMap<>();
static long res = 0;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
for (int i = 0; i < n-1; i++) {
int x = sc.nextInt(),y = sc.nextInt();
buildTree(x, y);
buildTree(y, x);
}
dfs(1, new boolean[n+1], 1);
System.out.println(res);
}
private static void dfs(int root, boolean[] flag,int parent) {
flag[root] = true;
List<Integer> list = m.get(root);
res += root-parent;
for (Integer integer : list) {
if(flag[integer])continue;
dfs(integer,flag,root);
}
}
private static void buildTree(int x, int y) {
List<Integer> list = m.get(x);
if(list==null)list = new ArrayList<>();
list.add(y);
m.put(x,list);
}
}
3.前缀和状压即可 public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String s = br.readLine();
int n = s.length();
long res = 0;int p = 0;
int[] ces = new int[1<<26];ces[0] = 1;
for (int i = 0; i < n; i++) {
int i1 = s.charAt(i) - 'a';
p^=1<<i1;
for (int j = 0; j < 26; j++) {
res+=ces[p^(1<<j)];
}
ces[p]++;
}
System.out.println(res);
}
前缀和求排列组合不也是On^2吗？求解惑
